Description

An $n \times m$ grid is given. The rows are numbered from $0$ to $n-1$ from top to bottom, and the columns are numbered from $0$ to $m-1$ from left to right. Initially, every cell is not an obstacle.

A path from the start $(0,0)$ to the end $(n-1,m-1)$ is defined to be valid if and only if it passes through exactly $n+m-1$ cells (including the start and the end), and each step moves either one cell to the right or one cell downward. Of course, the path cannot pass through obstacle cells (including the start and the end).

You have an $int$ variable $v = 0$. You need to simulate $k$ operations. Each operation gives three non-negative integers $r, c, z$. Let $x = (r \operatorname{xor} v) \bmod n$, $y = (c \operatorname{xor} v) \bmod m$:

1. If $(x,y)$ is an obstacle cell, ignore this operation and output NIE.
2. Otherwise, if after turning $(x,y)$ into an obstacle cell there still exists a valid path, then turn $(x,y)$ into an obstacle cell and output NIE.
3. Otherwise, if after turning $(x,y)$ into an obstacle cell there is no valid path, then output TAK, and update $v$ to $v \operatorname{xor} z$.

Input Format

The first line contains three positive integers $n, m, k$.

The next $k$ lines each contain three non-negative integers $r, c, z$.

Output Format

For each operation, output one line: TAK or NIE.

3 5 7
0 1 123
1 0 0
4 8 0
2 2 16
2 3 0
18 19 17
3 0 0

NIE
TAK
NIE
TAK
NIE
TAK
NIE

Hint

For $100\%$ of the testdata: $2 \le n, m \le 10^5$, $1 \le k \le 10^6$, $0 \le r, c, z < 2^{20}$.

Explanation:

Translated by ChatGPT 5