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 自动生成**