33124번 - Grid Game 3-angle 다국어

문제

Your friends, Anda and Kamu decide to play a game called Grid Game and ask you to become 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; the $c$^th cell of row $r$ is denoted as $(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 on it. You then give Anda and Kamu an integer $K$ and commence the game.

Anda and Kamu will take turns alternately with Anda taking the first turn. A player on their turn will do the following.

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

The following illustrations show all the possible cells in which you can add stones for $K = 3$. You choose the cell $(2, 1)$ for the left illustration and the cell $(4, 3)$ for the right illustration.

A player who is unable to complete their turn (because there are no more stones on the grid) will lose the game, and the opposing player wins. Determine who will win the game if both players play optimally.

입력

This problem is a multi-case problem. The first line consists of an integer $T$ (1ドル ≤ T ≤ 100$) that represents the number of test cases.

Each test case starts with a single line consisting of three integers $N$ $M$ $K$ (1ドル ≤ N ≤ 10^9$; 1ドル ≤ M, K ≤ 200,円 000$). Then, each of the next $M$ lines consists of three integers $R_i$ $C_i$ $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$ across all test cases does not exceed 200ドル,円 000$.

출력

For each case, output a string in a single line representing the player who will win the game if both players play optimally. Output Anda if Anda, the first player, wins. Otherwise, output Kamu.

제한

힌트