← 返回题目列表

AtCoder · arc155_d

D. 避免 Coprime 游戏

中文机器翻译题面 查看原题

分数: 800 点

问题陈述

对于两个非负整数 x 和 y,让 \gcd(x,y) 是最大公约数 x 和 y (对于 黑板上的 x=0,让 \gcd(x,y)=\gcd(y,x)=y).

有 N 整数,以及 i- 第一个整数是 A_i。这些的最大公约数 N 整数是 1.

高桥和青木将进行一场比赛。初始化一个整数后 G to 0,他们将轮流执行以下操作,高桥先进行。

  • 选择一个号码 a 在黑板上这样 \gcd(G,a)\neq 1,删除它并替换 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) is 1.
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 \dots A_N

输出

打印 N 行。的 i- 第行应包含获胜者的姓名, Takahashi or Aoki,当高桥选择 i第一回合黑板上的第一个整数,然后双方都发挥最佳状态。


示例输入 1

4
2 3 4 6

示例输出 1

Takahashi
Aoki
Takahashi
Aoki

例如,当高桥选择第四个整数时 A_4=6 在他的第一回合中,Aoki 可以选择第二个整数 A_2=3 使 G=3。现在,高桥无法选择任何东西,所以青木获胜。因此,第四行应该包含 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