配点 : $900$ 点

問題文

高橋君と青木君は、石取りゲームをしています。最初、山が $N$ 個あり、$i$ 個目の山には $A_i$ 個の石があり、整数 $K_i$ が定まっています。

高橋君と青木君は、高橋君から始めて、交互に以下の操作を繰り返します。

• 山を $1$ つ選ぶ。$i$ 個目の山を選び、その山に $X$ 個の石が残っている場合、$1$ 個以上 $floor(X/K_i)$ 個以下の任意の個数の石を $i$ 個目の山から取り除く。

先に操作ができなくなったプレイヤーが負けです。両者最善を尽くしたとき、どちらのプレイヤーが勝つか判定してください。 ただし、$floor(x)$ で $x$ 以下の最大の整数を表します。

制約

• $1 \leq N \leq 200$
• $1 \leq A_i,K_i \leq 10^9$
• 入力はすべて整数である

入力

入力は以下の形式で標準入力から与えられる。

$N$

$A_1$ $K_1$

$:$

$A_N$ $K_N$

出力

高橋君が勝つなら Takahashi を、青木君が勝つなら Aoki を出力せよ。

2
5 2
3 3

Aoki

最初、$1$ 個目の山からは $floor(5/2)=2$ 個まで、$2$ 個目の山からは $floor(3/3)=1$ 個までの石を一度に取り除くことができます。

• 高橋君が最初に $1$ 個目の山から $2$ 個の石を取ると、$1$ 個目の山からは $floor(3/2)=1$ 個まで、$2$ 個目の山からは $floor(3/3)=1$ 個までの石を一度に取り除くことができるようになります。
• 次に、青木君が $2$ 個目の山から $1$ 個の石を取ると、$1$ 個目の山からは $floor(3/2)=1$ 個までの石を取り除くことができ、$2$ 個目の山からは ($floor(2/3)=0$ より) 石を取り除くことができなくなります。
• 次に、高橋君が $1$ 個目の山から $1$ 個の石を取ると、$1$ 個目の山からは $floor(2/2)=1$ 個までの石を一度に取り除くことができるようになります。$2$ 個目の山からは石を取り除くことはできません。
• 次に、青木君が $1$ 個目の山から $1$ 個の石を取ると、$1$ 個目の山からは $floor(1/2)=0$ 個までの石を一度に取り除くことができるようになります。$2$ 個目の山からは石を取り除くことはできません。

これ以上の操作はできないため、青木君の勝ちです。高橋君がそれ以外の行動をした場合も、青木君はうまく行動を選ぶことで勝つことができます。

3
3 2
4 3
5 1

Takahashi

3
28 3
16 4
19 2

Aoki

4
3141 59
26535 897
93 23
8462 64

Takahashi