102556: [AtCoder]ABC255 G - Constrained Nim

Problem Statement

Takahashi and Aoki will play a game against each other using $N$ piles of stones.

Initially, for each $i = 1, 2, \ldots, N$, the $i$-th pile is composed of $A_i$ stones. The players alternately perform the following action, with Takahashi going first.

• Choose a pile with at least one stone remaining, and remove one or more stones.

However, there are $M$ forbidden moves.
For each $i = 1, 2, \ldots, M$, it is not allowed to remove exactly $Y_i$ stones from a pile composed of exactly $X_i$ stones.

The first player to become unable to perform the action loses, resulting in the other player's victory. Which player will win when both players employ the optimal strategy for the victory?

Constraints

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq M \leq 2 \times 10^5$
• $1 \leq A_i \leq 10^{18}$
• $1 \leq Y_i \leq X_i \leq 10^{18}$
• $i \neq j \Rightarrow (X_i, Y_i) \neq (X_j, Y_j)$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$ $M$
$A_1$ $A_2$ $\ldots$ $A_N$
$X_1$ $Y_1$
$X_2$ $Y_2$
$\vdots$
$X_M$ $Y_M$

Output

If Takahashi will win when both players employ the optimal strategy for the victory, print Takahashi; if Aoki will win, print Aoki.

Sample Input 1

3 4
1 2 4
2 1
3 3
3 1
1 1

Sample Output 1

Takahashi

For each $i = 1, 2, 3$, let $A'_i$ be the number of stones remaining in the $i$-th pile. Now, we use the sequence $A' = (A'_1, A'_2, A'_3)$ to represent the numbers of stones remaining in the piles.

Before the start of the game, we have $A' = (1, 2, 4)$. One possible progression of the game is as follows.

• First, Takahashi removes $1$ stone from the $3$-rd pile. Now, $A' = (1, 2, 3)$.
• Next, Aoki removes $2$ stones from the $2$-nd pile. Now, $A' = (1, 0, 3)$.
• Then, Takahashi removes $2$ stones from the $3$-rd pile. Now, $A' = (1, 0, 1)$.

At this point, the $1$-st and $3$-rd piles still have $1$ stone each, but it is forbidden ー as the fourth forbidden move ー to remove exactly $1$ stone from a pile composed of exactly $1$ stone, so Aoki cannot play. Thus, Takahashi wins.

Sample Input 2

1 5
5
5 1
5 2
5 3
5 4
5 5

Sample Output 2

Aoki

问题描述

高桥和青木将使用$N$堆石头进行游戏。

最初，对于每个$i = 1, 2, \ldots, N$，第$i$堆由$A_i$个石头组成。 玩家交替执行以下操作，由高桥先开始。

• 选择一堆至少剩下一块石头，然后移除一块或更多的石头。

但是，有$M$个禁止移动。
对于每个$i = 1, 2, \ldots, M$，不允许从由正好$X_i$块石头组成的堆中移除正好$Y_i$块石头。

当第一个玩家无法执行该操作时，他输掉比赛，导致另一个玩家获胜。 当双方都采用胜利的最优策略时，哪一方会赢？

约束条件

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq M \leq 2 \times 10^5$
• $1 \leq A_i \leq 10^{18}$
• $1 \leq Y_i \leq X_i \leq 10^{18}$
• $i \neq j \Rightarrow (X_i, Y_i) \neq (X_j, Y_j)$
• 输入中的所有值都是整数。

输入

输入以标准输入的以下格式给出：

$N$ $M$
$A_1$ $A_2$ $\ldots$ $A_N$
$X_1$ $Y_1$
$X_2$ $Y_2$
$\vdots$
$X_M$ $Y_M$

输出

如果当双方都采用胜利的最优策略时，高桥会赢，打印Takahashi；如果青木会赢，打印Aoki。

样例输入 1

3 4
1 2 4
2 1
3 3
3 1
1 1

样例输出 1

Takahashi

对于每个$i = 1, 2, 3$，令$A'_i$表示第$i$堆中剩余的石头数。现在，我们使用序列$A' = (A'_1, A'_2, A'_3)$表示堆中剩余的石头数。

在游戏开始之前，我们有$A' = (1, 2, 4)$。游戏的一种可能进程如下。

• 首先，高桥从第$3$堆中移除$1$块石头。现在，$A' = (1, 2, 3)$。
• 接下来，青木从第$2$堆中移除$2$块石头。现在，$A' = (1, 0, 3)$。
• 然后，高桥从第$3$堆中移除$2$块石头。现在，$A' = (1, 0, 1)$。

此时，第$1$堆和第$3$堆仍有$1$块石头，但从正好有$1$块石头的堆中移除正好$1$块石头是禁止的——因为第四个禁止移动——所以青木不能玩。因此，高桥获胜。

样例输入 2

1 5
5
5 1
5 2
5 3
5 4
5 5

样例输出 2

Aoki