Grid Obstacle Simulation

Given an $n\times m$ grid with rows numbered from $0$ to $n-1$ and columns numbered from $0$ to $m-1$, initially all cells are free (i.e. there are no obstacles). A path from $(0,0)$ to $(n-1,m-1)$ is defined as legal if and only if it contains exactly $n+m-1$ cells (including the start and end) and each step moves either one cell to the right or one cell down. Moreover, the path must not pass through any obstacles.

You start with an integer variable $v=0$. You are to simulate $k$ operations. Each operation provides three non-negative integers $r$, $c$, and $z$. For each operation, compute $$x = (r \operatorname{xor} v) \bmod n, \quad y = (c \operatorname{xor} v) \bmod m.$$ Then, follow these rules:

1. If cell $(x,y)$ is already an obstacle, ignore this operation and output NIE.
2. Otherwise, if changing cell $(x,y)$ into an obstacle still leaves at least one legal path from $(0,0)$ to $(n-1,m-1)$, then mark cell $(x,y)$ as an obstacle and output NIE.
3. If turning cell $(x,y)$ into an obstacle would result in no legal path being available, then output TAK and update the variable as $$v = v \operatorname{xor} z,$$ leaving cell $(x,y)$ unblocked.

Note: The starting cell $(0,0)$ and the ending cell $(n-1,m-1)$ must remain unobstructed in any legal path.

inputFormat

The first line contains three integers $n$, $m$, and $k$.
Each of the next $k$ lines contains three non-negative integers $r$, $c$, and $z$, representing an operation.

outputFormat

For each operation, output a line containing either TAK or NIE according to the rules described above.

sample

3 3 4
0 0 1
1 1 2
2 2 0
0 1 5

TAK
TAK
NIE
NIE