Grid Game 3-angle

Your friends, Anda and Kamu, want to play a game called Grid Game and ask you to be the gamemaster. As the gamemaster, you set up a triangular grid of size $N$. The grid has $N$ rows, numbered from $1$ to $N$. Row $r$ has $r$ cells, and the $c$th cell of row $r$ is denoted $(r, c)$.

Before the game starts, $M$ different cells (numbered from $1$ to $M$) are chosen. At cell $(R_i, C_i)$, you add $A_i$ stones. You then give Anda and Kamu an integer $K$ and start the game.

Anda and Kamu take turns, with Anda going first. On a turn, a player does the following.

• Chooses a cell $(r, c)$ with at least one stone on it.
• Removes at least one and at most $K$ stones from the chosen cell.
• For each cell $(x, y)$ with $r+1 ≤ x ≤ \min(N, r+K)$ and $c ≤ y ≤ c+x-r$, adds zero or more stones, but at most $K$, to that cell.

The following illustrations show all the cells where stones can be added for $K = 3$. The left one chooses cell $(2, 1)$, and the right one chooses cell $(4, 3)$.

A player who cannot complete a turn because no stones remain on the grid loses, and the opposing player wins. Determine who wins if both players play optimally.

The first line contains an integer $T$ ($1 ≤ T ≤ 100$), the number of test cases.

Each test case starts with a line containing three integers $N$, $M$, and $K$ ($1 ≤ N ≤ 10^9$; $1 ≤ M, K ≤ 200000$). Each of the next $M$ lines contains three integers $R_i$, $C_i$, and $A_i$ ($1 ≤ C_i ≤ R_i ≤ N$; $1 ≤ A_i ≤ 10^9$). The pairs $(R_i, C_i)$ are distinct.

The sum of $M$ over all test cases does not exceed 200000.

For each test case, output one line with the player who wins if both play optimally. Output Anda if Anda, the first player, wins. Otherwise, output Kamu.