← 返回题目列表

AtCoder · abc255_g

G. 约束尼姆

中文机器翻译题面 查看原题

分数: 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