CF2045F.Grid Game 3-angle

Anda 和 Kamu 决定玩一个叫作「网格游戏」的游戏，并请你来做裁判。作为裁判，你需要设置一个大小为 $N$ 的三角形网格。这个网格共有 $N$ 行（从 $1$ 到 $N$ 编号）。第 $r$ 行有 $r$ 个格子，第 $r$ 行的第 $c$ 个格子记作 $(r, c)$。

在开始游戏前，有 $M$ 个不同的格子被选中（编号从 $1$ 到 $M$），并在格子 $(R_i, C_i)$ 上放置 $A_i$ 颗石子。随后，你给 Anda 和 Kamu 一个整数 $K$，游戏随即开始。

玩家 Anda 和 Kamu 轮流进行游戏，由 Anda 先手。每个玩家在他的回合中必须：

• 选择一个至少包含一颗石子的格子 $(r, c)$；
• 从该格子中移除至少一颗但不超过 $K$ 颗石子；
• 对于每个满足 $r + 1 \leq x \leq \min(N, r + K)$ 且 $c \leq y \leq c + x - r$ 的格子 $(x, y)$，可以向其中添加零颗或多颗，但不超过 $K$ 颗的石子。

下图显示了当 $K = 3$ 时，可以添加石子的所有可能格子。左图选择了 $(2, 1)$，右图选择了 $(4, 3)$。

无法进行有效回合（即因为没有足够的石子）的一方将输掉比赛，而对方将获胜。请判断，如果双方都采取最佳策略，谁将赢得比赛。

本题包含多组测试数据。第一行是一个整数 $T$（$1 \leq T \leq 100$），表示测试数据的组数。

每组测试数据的第一行包含三个整数 $N$、$M$ 和 $K$（$1 \leq N \leq 10^9; 1 \leq M, K \leq 200\,000$）。接下来的 $M$ 行中，每行包含三个整数 $R_i$、$C_i$ 和 $A_i$（$1 \leq C_i \leq R_i \leq N; 1 \leq A_i \leq 10^9$）。每对 $(R_i, C_i)$ 都是独特的。

所有测试数据中 $M$ 的总和不超过 $200\,000$。

对于每组测试数据，输出一行字符串，表示如果双方都采取最佳策略，哪位玩家将赢得比赛。如果 Anda 获胜，输出“Anda”；否则，输出“Kamu”。

示例说明

对于第一个例子，Anda 在第一回合将从格子 $(1, 1)$ 移除所有石子，然后在 $(2, 1)$ 添加三颗石子。此时，唯一剩余的有石子的格子是 $(2, 1)$，其中有五颗石子，因此 Kamu 必须在该回合中从中移除石子。无论 Kamu 移除多少，Anda 都能在随后一回合中移除剩下的所有石子，从而赢得比赛。

对于第二个例子，Kamu 可以通过模仿 Anda 的所有操作，即使 Anda 无法完成回合，使得自己成为胜利者。

本翻译由 AI 自动生成