P15673 [ICPC 2024 Jakarta R] Grid Game 3-angle

你的朋友 Anda 和 Kamu 决定玩一个名为 Grid Game 的游戏，并邀请你担任游戏主持人。作为主持人，你设置了一个大小为 $N$ 的三角形网格。该网格有 $N$ 行（编号从 $1$ 到 $N$）。第 $r$ 行有 $r$ 个单元格；第 $r$ 行的第 $c$ 个单元格记为 $(r, c)$。 :::align{center}  ::: 在游戏开始前，选择了 $M$ 个不同的单元格（编号从 $1$ 到 $M$）：在单元格 $(R_i, C_i)$ 上，你放置了 $A_i$ 颗石子。然后你给 Anda 和 Kamu 一个整数 $K$，并开始游戏。 Anda 和 Kamu 将轮流进行，Anda 先手。轮到一名玩家时，他需要执行以下操作： - 选择一个至少有一颗石子的单元格 $(r, c)$。 - 从选定的单元格中移除至少 $1$ 颗、至多 $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)$。 :::align{center}  ::: 如果一名玩家无法完成他的回合（因为网格上已经没有石子了），则该玩家输掉游戏，对手获胜。假设双方都采取最优策略，请确定谁会赢得游戏。

本题包含多组测试数据。第一行包含一个整数 $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。

**样例输入/输出 #1 的解释** 对于第一个测试用例，在第一回合中，Anda 将移除单元格 $(1, 1)$ 中的所有石子，然后在 $(2, 1)$ 上添加三颗石子。现在唯一剩下石子的单元格是 $(2, 1)$，共有五颗石子，因此 Kamu 必须从该单元格移除石子。无论 Kamu 移除多少颗石子，Anda 都可以移除 $(2, 1)$ 中剩余的所有石子并赢得游戏。 对于第二个测试用例，Kamu 总是可以镜像模仿 Anda 的每一步操作，直到 Anda 无法完成他的回合为止。 翻译由 DeepSeek V3.2 完成