分数: 600 点
问题陈述
高桥和青木将使用 N 成堆的石头。
最初,对于每个 i = 1, 2, \ldots, N, i第堆由以下组成 A_i 石头。 玩家们交替执行以下动作,高桥先行。
- 选择一堆至少剩余一颗石子,并移除一颗或多颗石子。
但是,有 M 禁止的动作。
对于每个 i = 1, 2, \ldots, M,不允许精确删除 Y_i 由一堆石头组成 X_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 获胜,则打印 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)。游戏的一种可能的进展如下。
- 首先,高桥删除 1 石头来自 3-rd 堆。现在, A' = (1, 2, 3).
- 接下来,青木删除 2 石头来自 2-nd 堆。现在, A' = (1, 0, 3).
- 然后,高桥删除 2 石头来自 3-rd 堆。现在, A' = (1, 0, 1).
此时, 1-st 和 3-rd 堆仍然有 1 每个石头,但禁止作为第四个禁止移动,准确移除 1 石头由一堆组成 1 石头,所以青木不能玩。因此,高桥获胜。
示例输入 2
1 5 5 5 1 5 2 5 3 5 4 5 5
示例输出 2
Aoki