{"problem":{"name":"Decrementing","description":{"content":"There are $N$ integers written on a blackboard. The $i$\\-th integer is $A_i$, and the greatest common divisor of these integers is $1$. Takahashi and Aoki will play a game using these integers. In thi","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc010_d"},"statements":[{"statement_type":"Markdown","content":"There are $N$ integers written on a blackboard. The $i$\\-th integer is $A_i$, and the greatest common divisor of these integers is $1$.\nTakahashi and Aoki will play a game using these integers. In this game, starting from Takahashi the two player alternately perform the following operation:\n\n*   Select one integer on the blackboard that is not less than $2$, and subtract $1$ from the integer.\n*   Then, divide all the integers on the black board by $g$, where $g$ is the greatest common divisor of the integers written on the blackboard.\n\nThe player who is left with only $1$s on the blackboard and thus cannot perform the operation, loses the game. Assuming that both players play optimally, determine the winner of the game.\n\n## Constraints\n\n*   $1 ≦ N ≦ 10^5$\n*   $1 ≦ A_i ≦ 10^9$\n*   The greatest common divisor of the integers from $A_1$ through $A_N$ is $1$.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$\n$A_1$ $A_2$ … $A_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc010_d","tags":[],"sample_group":[["3\n3 6 7","First\n\nTakahashi, the first player, can win as follows:\n\n*   Takahashi subtracts $1$ from $7$. Then, the integers become: $(1,2,2)$.\n*   Aoki subtracts $1$ from $2$. Then, the integers become: $(1,1,2)$.\n*   Takahashi subtracts $1$ from $2$. Then, the integers become: $(1,1,1)$."],["4\n1 2 4 8","First"],["5\n7 8 8 8 8","Second"]],"created_at":"2026-03-03 11:01:13"}}