I - Exchange Game Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

高橋君と青木君が、数の書かれたカードを使ってゲームをします。

最初、高橋君は A_1,\ldots,A_N が書かれた N 枚のカードを、青木君は B_1,\ldots,B_M が書かれた M 枚のカードを手札として持っており、場には C_1,\ldots,C_L が書かれた L 枚のカードがあります。
高橋君と青木君はゲーム中常に、相手の手札も含め、全てのカードに書かれた数を知っている状態にあります。

高橋君と青木君は、高橋君から順に次の行動を交互に行います。

  • 自分の手札から 1 枚選び場に出す。その後、出したカードに書かれていた数未満の数が書かれたカードが場にあれば、そのうち 1 枚を場から自分の手札に移して良い。

先に行動が行えなくなった方が負けであり、負けでない方が勝ちです。互いに最適に行動したとき、どちらが勝つか判定してください。

なおこのゲームは必ず有限回の行動で勝敗がつくことが証明できます。

制約

  • 1 \leq N,M,L
  • N+M+L \leq 12
  • 1 \leq A_i,B_i,C_i \leq 10^9
  • 入力は全て整数である

入力

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

N M L
A_1 \ldots A_N
B_1 \ldots B_M
C_1 \ldots C_L

出力

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

入力例 1

1 1 2
2
4
1 3

出力例 1

Aoki

ゲームは例えば次のように進行します。(最適な行動とは限りません)

  • 高橋君が手札から 2 を場に出し、1 を場から自分の手札に移す。高橋君の手札は (1)、青木君の手札は (4)、場札は (2,3) となる。
  • 青木君が手札から 4 を場に出し、2 を場から自分の手札に移す。高橋君の手札は (1)、青木君の手札は (2)、場札は (3,4) となる。
  • 高橋君が手札から 1 を場に出す。高橋君の手札は ()、青木君の手札は (2)、場札は (1,3,4) となる。
  • 青木君が手札から 2 を場に出す。高橋君の手札は ()、青木君の手札は ()、場札は (1,2,3,4) となる。
  • 高橋君は行動できないため負けであり、青木君が勝ち。

入力例 2

4 4 4
98 98765 987654 987654321
987 9876 9876543 98765432
123 12345 1234567 123456789

出力例 2

Takahashi

入力例 3

1 1 8
10
10
1 2 3 4 5 6 7 8

出力例 3

Aoki

Score : 500 points

Problem Statement

Takahashi and Aoki will play a game using cards with numbers written on them.

Initially, Takahashi has N cards with numbers A_1, \ldots, A_N in his hand, Aoki has M cards with numbers B_1, \ldots, B_M in his hand, and there are L cards with numbers C_1, \ldots, C_L on the table.
Throughout the game, both Takahashi and Aoki know all the numbers on all the cards, including the opponent's hand.

Starting with Takahashi, they take turns performing the following action:

  • Choose one card from his hand and put it on the table. Then, if there is a card on the table with a number less than the number on the card he just played, he may take one such card from the table into his hand.

The player who cannot make a move first loses, and the other player wins. Determine who wins if both players play optimally.

It can be proved that the game always ends in a finite number of moves.

Constraints

  • 1 \leq N, M, L
  • N + M + L \leq 12
  • 1 \leq A_i, B_i, C_i \leq 10^9
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N M L
A_1 \ldots A_N
B_1 \ldots B_M
C_1 \ldots C_L

Output

Print Takahashi if Takahashi wins, and Aoki if Aoki wins.

Sample Input 1

1 1 2
2
4
1 3

Sample Output 1

Aoki

The game may proceed as follows (not necessarily optimal moves):

  • Takahashi plays 2 from his hand to the table, and takes 1 from the table into his hand. Now, Takahashi's hand is (1), Aoki's hand is (4), and the table cards are (2,3).
  • Aoki plays 4 from his hand to the table, and takes 2 into his hand. Now, Takahashi's hand is (1), Aoki's hand is (2), and the table cards are (3,4).
  • Takahashi plays 1 from his hand to the table. Now, Takahashi's hand is (), Aoki's hand is (2), and the table cards are (1,3,4).
  • Aoki plays 2 from his hand to the table. Now, Takahashi's hand is (), Aoki's hand is (), and the table cards are (1,2,3,4).
  • Takahashi cannot make a move and loses; Aoki wins.

Sample Input 2

4 4 4
98 98765 987654 987654321
987 9876 9876543 98765432
123 12345 1234567 123456789

Sample Output 2

Takahashi

Sample Input 3

1 1 8
10
10
1 2 3 4 5 6 7 8

Sample Output 3

Aoki