题目描述

$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 \operatorname{xor} v)\bmod n,y=(c \operatorname{xor} v)\bmod m$：

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

输入格式

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

接下来 $k$ 行，每行三个非负整数 $r,c,z$。

输出格式

对于每个操作输出一行 TAK 或 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

提示

对于 $100\%$ 的数据,$2\le n,m\le 10^5$， $1\le k\le 10^6$，$0\le r,c,z<2^{20}$。

解释：