题目描述

题目译自 PA 2019 Runda 5 Osady i warownie 2

有个 $n \times m$ 的网格，从上到下依次为第 $0$ 到 $n - 1$ 行，从左到右依次为第 $0$ 到 $m - 1$ 列，一开始每个点都不是障碍格。

定义一条从起点 $(0, 0)$ 到终点 $(n - 1, m - 1)$ 的路径是合法的，当且仅当这条路径经过恰好 $n + m - 1$ 个格子（包括起点和终点），且每一步要么往右走一格，要么往下走一格。当然，这条路径不能经过障碍格（包括起点和终点）。

你有一个 int 类型的变量 $v = 0$，你现在需要模拟 $k$ 次操作，每次操作会给出三个非负整数 $r, c, z$，令 $x = (r \oplus v) \bmod n, y = (c \oplus v) \bmod m$，其中 $\oplus$ 代表异或位运算：

1. 如果 $(x, y)$ 是障碍格，那么忽略这次操作，输出 NIE。
2. 否则如果将 $(x, y)$ 变成障碍格后仍然存在合法路径，那么将 $(x, y)$ 变成障碍格，输出 NIE。
3. 否则如果将 $(x, y)$ 变成障碍格后不存在合法路径，那么忽略这次操作，然后输出 TAK 并将 $v$ 修改为 $v \oplus z$。

输入格式

第一行三个正整数 $n, m, k$。

接下来 $k$ 行，每行三个非负整数 $r, c, z$，含义如题面所述。

输出格式

输出 $k$ 行，每行一个单词 TAK 或 NIE，表示对这 $k$ 步操作的回答。

样例

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

数据范围与提示

对于所有数据，$2 \le n, m \le 10^5, 1 \le k \le 10^6, 0 \le r, c, z < 2^{20}$；

其中有 $50$ 分的数据，满足 $n\cdot m\le 2.5\times 10^7$。