A - 石取りゲーム 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 233 点

問題文

高橋君と青木君が石取りゲームで対戦します。

テーブルの上に N 個の石の山があり、それぞれの山には 1 から N までの番号が付けられています。山 i には A_i 個の石が積まれています。

ゲームは高橋君から始まり、二人は交互に以下の操作を行います：

  • まだ石が残っている山を 1 つ選び、その山から石を 1 個取り除く。
  • 石が 0 個になった山は空になり、以降選ぶことができなくなる。

すべての山が空になったとき、最後の石を取ったプレイヤーが勝ちとなります。

両者が最適に行動したとき、どちらのプレイヤーが勝つか判定してください。

制約

  • 1 \leq N \leq 10^5
  • 1 \leq A_i \leq 10^9
  • 入力はすべて整数

入力

N
A_1 A_2 \ldots A_N
  • 1 行目には、石の山の数 N が与えられる。
  • 2 行目には、各山の石の個数を表す A_1, A_2, \ldots, A_N がスペース区切りで与えられる。

出力

高橋君が勝つ場合は Takahashi と、青木君が勝つ場合は Aoki と出力してください。

入力例 1

3
1 2 1

出力例 1

Aoki

入力例 2

2
3 4

出力例 2

Takahashi

入力例 3

8
7 1 4 2 6 3 5 8

出力例 3

Aoki

入力例 4

20
1000000000 999999999 123456789 987654321 500000000 400000000 300000000 200000000 100000000 999999998 7654321 8765432 135791357 246802468 111111111 222222222 333333333 444444444 555555555 666666667

出力例 4

Takahashi

入力例 5

1
1000000000

出力例 5

Aoki

Score : 233 pts

Problem Statement

Takahashi and Aoki are playing a stone taking game.

There are N piles of stones on the table, and each pile is numbered from 1 to N. Pile i contains A_i stones.

The game starts with Takahashi, and the two players alternately perform the following operation:

  • Choose one pile that still has stones remaining, and remove 1 stone from that pile.
  • A pile with 0 stones becomes empty and can no longer be chosen.

When all piles become empty, the player who took the last stone wins.

Determine which player wins when both players play optimally.

Constraints

  • 1 \leq N \leq 10^5
  • 1 \leq A_i \leq 10^9
  • All inputs are integers

Input

N
A_1 A_2 \ldots A_N
  • The first line gives the number of piles of stones N.
  • The second line gives A_1, A_2, \ldots, A_N, the number of stones in each pile, separated by spaces.

Output

If Takahashi wins, print Takahashi. If Aoki wins, print Aoki.

Sample Input 1

3
1 2 1

Sample Output 1

Aoki

Sample Input 2

2
3 4

Sample Output 2

Takahashi

Sample Input 3

8
7 1 4 2 6 3 5 8

Sample Output 3

Aoki

Sample Input 4

20
1000000000 999999999 123456789 987654321 500000000 400000000 300000000 200000000 100000000 999999998 7654321 8765432 135791357 246802468 111111111 222222222 333333333 444444444 555555555 666666667

Sample Output 4

Takahashi

Sample Input 5

1
1000000000

Sample Output 5

Aoki