当前没有测试数据。

G - 受限Nim

分数：$600$ 分

问题描述

高桥和青木将使用 $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。

3 4
1 2 4
2 1
3 3
3 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$ 种操作被禁止，因此青木无法行动。因此，高桥获胜。

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

Aoki