/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
2 つの非負整数 x, y に対し \gcd(x,y) を x と y の最大公約数とします（ただし、 x=0 のときは \gcd(x,y)=\gcd(y,x)=y とします）。
黒板に N 個の整数が書かれており、そのうち i 番目の整数は A_i です。これら N 個の整数の最大公約数は 1 です。
高橋君と青木君が 2 人で対戦ゲームをします。整数 G を G=0 で初期化した後、2 人は高橋君から始めて交互に以下の操作を繰り返します。
- 黒板に書かれている数のうち、\gcd(G,a)\neq 1 をみたす数 a を選んで消し、G を \gcd(G,a) で置き換える。
先に操作を行えなくなったほうが負けです。
各 i\ (1\leq i \leq N) について、高橋君が最初の手番で i 番目の整数を選んだ後、両者が最善を尽くした場合、どちらが勝つか判定してください。
制約
- 2 \leq N \leq 2 \times 10^5
- 2 \leq A_i \leq 2 \times 10^5
- N 個の整数 A_i \ (1\leq i \leq N) の最大公約数は 1
- 与えられる入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \dots A_N
出力
N 行出力せよ。i 行目には高橋君が最初の手番で i 番目の整数を選んだ後、両者が最善を尽くした場合、高橋君が勝つ場合は Takahashi を、青木君が勝つ場合は Aoki を出力せよ。
入力例 1
4 2 3 4 6
出力例 1
Takahashi Aoki Takahashi Aoki
例えば高橋君が最初の手番で 4 番目の整数 A_4=6 を選んだ場合、青木君が 2 番目の整数 A_2=3 を選ぶと G=3 となります。この後高橋君が選べる整数は存在しないので、青木君の勝利となります。よって 4 行目には Aoki を出力します。
入力例 2
4 2 155 155 155
出力例 2
Takahashi Takahashi Takahashi Takahashi
黒板には同じ整数が複数個書かれていることがあります。
入力例 3
20 2579 25823 32197 55685 73127 73393 74033 95252 104289 114619 139903 144912 147663 149390 155806 169494 175264 181477 189686 196663
出力例 3
Takahashi Aoki Takahashi Aoki Takahashi Takahashi Takahashi Takahashi Aoki Takahashi Takahashi Aoki Aoki Aoki Aoki Aoki Takahashi Takahashi Aoki Takahashi
Score : 800 points
Problem Statement
For two non-negative integers x and y, let \gcd(x,y) be the greatest common divisor of x and y (for x=0, let \gcd(x,y)=\gcd(y,x)=y).
There are N integers on the blackboard, and the i-th integer is A_i. The greatest common divisor of these N integers is 1.
Takahashi and Aoki will play a game against each other. After initializing an integer G to 0, they will take turns performing the following operation, with Takahashi going first.
- Choose a number a on the blackboard such that \gcd(G,a)\neq 1, erase it, and replace G with \gcd(G,a).
The first player unable to play loses.
For each i\ (1\leq i \leq N), determine the winner when Takahashi chooses the i-th integer on the blackboard in his first turn, and then both players play optimally.
Constraints
- 2 \leq N \leq 2 \times 10^5
- 2 \leq A_i \leq 2 \times 10^5
- The greatest common divisor of the N integers A_i \ (1\leq i \leq N) is 1.
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \dots A_N
Output
Print N lines. The i-th line should contain the winner's name, Takahashi or Aoki, when Takahashi chooses the i-th integer on the blackboard in his first turn, and then both players play optimally.
Sample Input 1
4 2 3 4 6
Sample Output 1
Takahashi Aoki Takahashi Aoki
For instance, when Takahashi chooses the fourth integer A_4=6 in his first turn, Aoki can then choose the second integer A_2=3 to make G=3. Now, Takahashi cannot choose anything, so Aoki wins. Thus, the fourth line should contain Aoki.
Sample Input 2
4 2 155 155 155
Sample Output 2
Takahashi Takahashi Takahashi Takahashi
The blackboard may contain the same integer multiple times.
Sample Input 3
20 2579 25823 32197 55685 73127 73393 74033 95252 104289 114619 139903 144912 147663 149390 155806 169494 175264 181477 189686 196663
Sample Output 3
Takahashi Aoki Takahashi Aoki Takahashi Takahashi Takahashi Takahashi Aoki Takahashi Takahashi Aoki Aoki Aoki Aoki Aoki Takahashi Takahashi Aoki Takahashi