AT_kupc2018_j.ニム?

有 $N$ 堆硬币。

每堆硬币分别编号为 $1$ 到 $N$，第 $i$ 堆包含 $a_i$ 枚硬币。

我们要考虑一种由两名玩家进行的游戏，游戏规则如下：

• 两名玩家分别为先手和后手。
• 游戏从先手开始，双方轮流进行以下操作：
  1. 确定一个正整数 $x$，$x$ 不超过 $K$。注意，从第二次操作开始，每次选择的 $x$ 不能比上一次操作选的更小。
  2. 选择一个至少包含 $x$ 枚硬币的堆，并从中移除 $x$ 枚硬币。如果无法找到这样的堆，游戏结束，对方胜利。

千夏和亚加里决定进行 $M$ 次这样的游戏，每局游戏都是千夏先手，亚加里后手。

每局游戏结束后，本局移除的硬币会被放回原堆。

为了避免每局结果都一样，从而让游戏失去趣味，他们在第 $i$ $(1 \leq i \leq M - 1)$ 次游戏之后，会在将硬币放回后，选择第 $b_i$ 堆增加 $c_i$ 枚硬币。

请判断在 $M$ 次游戏中，每局游戏千夏（先手）和亚加里（后手）谁能获得胜利。

从标准输入中给出如下信息：

$N$ $K$ $M$ $a_1$ $a_2$ $\ldots$ $a_N$ $b_1$ $c_1$ $\ldots$ $b_{M-1}$ $c_{M-1}$

对第 $i$ 局游戏，如果千夏（先手）获胜，输出 Chinatsu；如果亚加里（后手）获胜，输出 Akari。

约束条件

• 全部输入均为整数。
• $1 \leq N \leq 10^5$
• $1 \leq K \leq 10^9$
• $1 \leq M \leq 10^5$
• $1 \leq a_i \leq 10^9$
• $1 \leq b_i \leq N$
• $1 \leq c_i \leq 10^9$

部分分数

如果正确解出附加约束条件下的数据集，将获得 $30$ 分：

• $N = 1$
• $M = 1$

解出不带附加约束条件的数据集，将获得额外 $370$ 分。

样例解释

• 示例 1：千夏作为先手，在第一次操作中就能移除唯一的那堆中的所有硬币。这样亚加里无法进行任何有效的操作，因此千夏获胜。这个输入满足部分分数的附加条件。
• 示例 2：两人只能选择 $1$。第一回合千夏从堆中移除 $1$ 枚硬币，而后亚加里再移除最后 $1$ 枚。第二回合千夏无法找到可以操作的堆，因此亚加里获胜。此输入满足部分分数的附加条件。

本翻译由 AI 自动生成