你的朋友 Anda 和 Kamu 决定玩一款名为 Grid Game 的游戏,并要求你成为游戏管理员。作为游戏管理员,您设置了一个大小为 $$$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$$$ 的石头。
- 对于每个单元格 $$$(x, y)$$$,使得 $$$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_1 \leq 10^9$$$) 组成。 $$$(R_i, C_i)$$$ 对是不同的。
所有测试用例的 $$$M$$$ 总和不超过 $$$200\,000$$$。
输出
对于每种情况,在一行中输出一个字符串,表示如果两个玩家都发挥最佳,则将赢得游戏的玩家。如果第一个玩家 Anda 获胜,则输出 Anda。否则,输出Kamu。
示例
输入 #1
3 2 2 4 1 1 3 2 1 2 100 2 1 4 1 10 4 4 10 10 5 2 1 1 4 3 1 2 4 2 5 2 2 1 5 3 4
输出 #1
Anda Kamu Anda
注意
示例输入/输出#1 的说明
对于第一种情况,在第一回合中,Anda 会移除单元格 $$$(1, 1)$$$ 中的所有石子,然后在 $$$(2, 1)$$$ 处添加三颗石子。现在唯一剩下石头的格子是 $$$(2, 1)$$$ 格子,里面有五个石头,所以 Kamu 必须从该格子中移除石头。无论卡姆移走多少石子,安达都可以在 $$$(2, 1)$$$ 处移走所有剩余的石子并赢得比赛。
对于第二种情况,Kamu 始终可以模仿 Anda 做出的任何动作,直到 Anda 无法完成他们的回合。