Grid Game 3-angle

Anda와 Kamu는 Grid Game이라는 게임을 하려고 하며, 두 사람은 당신에게 진행자 역할을 맡겼다. 진행자는 크기가 $N$인 삼각형 격자를 만든다. 격자에는 $N$개의 행이 있고 1번부터 $N$번까지 번호가 붙는다. $r$행에는 $r$개의 칸이 있으며, $r$행의 $c$번째 칸을 $(r, c)$로 나타낸다.

게임을 시작하기 전에 서로 다른 $M$개의 칸(1번부터 $M$번까지 번호가 붙음)을 고른다. 칸 $(R_i, C_i)$에 $A_i$개의 돌을 올린다. 그다음 정수 $K$를 Anda와 Kamu에게 알려주고 게임을 시작한다.

Anda와 Kamu는 번갈아 두며, Anda가 먼저 둔다. 한 차례에 플레이어는 다음을 수행한다.

• 돌이 하나 이상 놓여 있는 칸 $(r, c)$를 고른다.
• 고른 칸에서 돌을 한 개 이상, $K$개 이하로 제거한다.
• $r+1 ≤ x ≤ \min(N, r+K)$이고 $c ≤ y ≤ c+x-r$인 각 칸 $(x, y)$에 돌을 0개 이상, $K$개 이하로 추가한다.

다음 그림은 $K = 3$일 때 돌을 추가할 수 있는 칸을 모두 보여준다. 왼쪽 그림은 칸 $(2, 1)$을 고른 경우이고, 오른쪽 그림은 칸 $(4, 3)$을 고른 경우이다.

격자에 돌이 남아 있지 않아 차례를 마치지 못하는 플레이어는 진다. 그러면 상대 플레이어가 이긴다. 두 플레이어가 최선을 다할 때 누가 이기는지 구하라.

첫 줄에 테스트 케이스의 개수를 나타내는 정수 $T$ ($1 ≤ T ≤ 100$)가 주어진다.

각 테스트 케이스의 첫 줄에는 정수 $N$, $M$, $K$ ($1 ≤ N ≤ 10^9$; $1 ≤ M, K ≤ 200000$)가 주어진다. 이어지는 $M$개의 줄에는 각각 정수 $R_i$, $C_i$, $A_i$ ($1 ≤ C_i ≤ R_i ≤ N$; $1 ≤ A_i ≤ 10^9$)가 주어진다. 쌍 $(R_i, C_i)$는 모두 서로 다르다.

모든 테스트 케이스의 $M$ 합은 200000을 넘지 않는다.

각 테스트 케이스마다 두 플레이어가 최선을 다할 때 이기는 플레이어를 한 줄에 출력한다. 선공인 Anda가 이기면 Anda를, 그렇지 않으면 Kamu를 출력한다.