AT_arc155_d.[ARC155D] Avoid Coprime Game

对于两个非负整数 $x, y$，$\gcd(x, y)$ 表示 $x$ 和 $y$ 的最大公约数（其中，当 $x=0$ 时，$\gcd(x, y)=\gcd(y, x)=y$）。

黑板上写有 $N$ 个整数，第 $i$ 个整数为 $A_i$。这 $N$ 个整数的最大公约数为 $1$。

高桥君和青木君进行一场对战游戏。初始时整数 $G=0$，两人轮流操作，高桥君先手。每次操作如下：

• 从黑板上选择一个满足 $\gcd(G, a) \neq 1$ 的数 $a$，将其擦去，并用 $\gcd(G, a)$ 替换 $G$。

无法进行操作的一方判负。

对于每个 $i\ (1\leq i \leq N)$，请判断如果高桥君在第一回合选择第 $i$ 个整数，之后双方都采取最优策略，最终谁会获胜。

输入通过标准输入给出，格式如下：

$N$ $A_1$ $A_2$ $\dots$ $A_N$

输出 $N$ 行。第 $i$ 行输出高桥君在第一回合选择第 $i$ 个整数后，双方都采取最优策略时的胜者。如果高桥君获胜，输出 Takahashi；如果青木君获胜，输出 Aoki。

限制条件

• $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$
• 输入均为整数

样例解释 1

例如，如果高桥君在第一回合选择第 $4$ 个整数 $A_4=6$，青木君可以选择第 $2$ 个整数 $A_2=3$，此时 $G=3$。之后高桥君无法再选择任何整数，因此青木君获胜。所以第 $4$ 行应输出 Aoki。

样例解释 2

黑板上可能会有多个相同的整数。

由 ChatGPT 4.1 翻译