受限 Nim

题目描述

高桥君和青木君使用由若干石子组成的 $N$ 堆石子进行取石子游戏对决。

初始时，对每个 $i = 1, 2, \ldots, N$，第 $i$ 堆有 $A_i$ 个石子。

两人从高桥君开始交替执行以下行动：

• 选择一堆至少还剩 1 个石子的石堆，从中取走 1 个或更多石子。

不过，这个游戏有 $M$ 种禁止操作，不允许执行属于禁止操作的行动。

对每个 $i = 1, 2, \ldots, M$，第 $i$ 种禁止操作是「从恰好有 $X_i$ 个石子的石堆中恰好取走 $Y_i$ 个石子」。

先无法行动的一方输，另一方获胜。

当双方都采取最优策略以争取胜利时，哪一方会获胜？

输入格式

输入按以下格式从标准输入给出：

N M
A_1 A_2 … A_N
X_1 Y_1
X_2 Y_2
⋮
X_M Y_M

输出格式

当双方都采取最优策略时，如果高桥君获胜输出 Takahashi，如果青木君获胜输出 Aoki。

样例

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

Takahashi

对每个 $i = 1, 2, 3$，设第 $i$ 堆剩下的石子数为 $A'_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 个石子」属于第 4 种禁止操作，因此青木君无法行动。于是高桥君获胜。

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

Aoki

数据范围

• $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$，则 $(X_i, Y_i) \neq (X_j, Y_j)$。
• 输入中的所有值均为整数。