103805: [Atcoder]ABC380 F - Exchange Game

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

问题陈述

高桥和青木将使用写有数字的卡片进行游戏。

最初，高桥手中有N张卡片，数字分别为$A_1, \ldots, A_N$，青木手中有M张卡片，数字分别为$B_1, \ldots, B_M$，桌子上还有L张卡片，数字分别为$C_1, \ldots, C_L$。
在整个游戏过程中，高桥和青木都知道所有卡片上的数字，包括对手手中的数字。

从高桥开始，他们轮流执行以下操作：

• 从手中选择一张卡片放在桌子上。然后，如果桌子上有一张数字小于他刚出的卡片的卡片，他可以从桌子上拿一张这样的卡片到手。

第一个无法进行操作的玩家输，另一个玩家赢。如果双方都采取最优策略，确定谁会赢。

可以证明游戏总是在有限步数内结束。

约束条件

• $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$

输出

如果高桥赢，打印，如果青木赢，打印。

样本输入1

1 1 2
2
4
1 3

样本输出1

青木

游戏可能按以下方式进行（不一定是最佳移动）：

• 高桥从手中打出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

高桥

样本输入3

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

样本输出3

青木