A93469.abc255G - Constrained Nim

问题陈述

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

输出

如果高桥和青木都采用最优策略获胜，则打印 "高桥"；如果青木获胜，则打印 "青木"。

样例一解释

对于每一个 $i = 1, 2, 3$ ，让 $A'_i$ 成为 $i$ /-堆中剩余的石子数量。现在，我们用序列 $A' = (A'_1, A'_2, A'_3)$ 来表示石堆中剩余石块的数量。

在棋局开始之前，我们有 $A' = (1, 2, 4)$ 颗棋子。对局的一种可能进展如下。

• 首先，高桥（Takahashi）从 $3$ （rd）这堆棋子中取出 $1$ 颗棋子。现在是 $A' = (1, 2, 3)$ 。
• 接下来，青木从 $2$ （后）这堆棋子中取出 $2$ 颗棋子。现在是 $A' = (1, 0, 3)$ .
• 然后，高桥从 $3$ 子堆中取出 $2$ 颗棋子现在 $A' = (1, 0, 1)$ .

此时， $1$ /st和 $3$ /rd这两堆棋子中仍然各有 $1$ 颗棋子，但是作为第四步禁手，从正好由 $1$ 颗棋子组成的棋堆中正好取出 $1$ 颗棋子是被禁止的，因此青木无法下棋。这样，高桥就赢了。