如大家所知，拜特国（Bajtocja）的行政区域内坐落着巨字节岛（Wyspa Megabajtocka）。该岛呈高为 $n$、宽为 $m$ 的矩形，被划分为 $n \cdot m$ 个单位正方形行政区域，排列成 $n$ 行 $m$ 列。行从北到南编号为 $0$ 到 $n-1$，列从西到东编号为 $0$ 到 $m-1$。位于第 $i$ 行第 $j$ 列的行政区域记为 $(i, j)$。

多年前，该岛曾是主要的贸易中心之一，但如今岛上仅存两座主要港口定居点，分别位于坐标 $(0, 0)$ 和 $(n-1, m-1)$ 处。陆路贸易与海路贸易同样重要，因此在两座定居点之间存在一条便捷的贸易路线至关重要。所谓便捷的贸易路线，是指满足以下条件的行政区域序列： 序列起始于区域 $(0, 0)$； 序列终止于区域 $(n-1, m-1)$； 序列中任意两个相邻区域在边上相邻； 序列恰好包含 $n+m-1$ 个区域，即它是最短的； * 序列不包含被敌方要塞占据的区域（下文将详细说明）。

巨字节海（Morze Gigabajtowe）的战略位置使巨字节岛成为拜特国敌人的诱人目标，他们计划入侵该岛并开始建造要塞。得益于空中支援，他们可以出现在任何地方，而不仅仅是在岸边！

幸运的是，拜特国拥有一种秘密武器——特殊的“拜特雷霆”（Bajtogrom）部队。如果某座敌方要塞建成后，导致两座港口定居点之间的便捷贸易路线不再存在（且仅在这种情况下！），拜特雷霆的士兵会立即出动，瞬间摧毁这座新建的要塞，只留下一片废墟。

整个拜特国（至少是巨字节岛）的命运掌握在你的手中！给定敌方要塞建造的先后顺序，你需要确定哪些要塞应该被拜特雷霆立即摧毁。

敌人尚未确定具体的攻击计划。有趣的是，每一座后续要塞的位置取决于之前哪些尝试引发了拜特雷霆的干预。敌人维护一个初始值为 $0$ 的变量 $x$。在第 $i$ 步，要塞将建在区域： $$((r_i \oplus x) \bmod n, (c_i \oplus x) \bmod m)$$ 如果拜特雷霆采取武装行动，则会将 $x$ 的值更新为 $x \oplus z_i$。上述公式中的 $\oplus$ 运算表示异或（xor）。

你可以假设敌人永远不会尝试在港口定居点、现有要塞或已摧毁要塞的废墟所在的区域建造要塞。换句话说，在解码后的区域序列中，没有重复项，且不包含 $(0, 0)$ 或 $(n-1, m-1)$。

输入格式

输入的第一行包含三个整数 $n, m$ 和 $k$ ($2 \le n, m \le 100\,000, 1 \le k \le 1\,000\,000$)，分别表示巨字节岛的尺寸和敌国将建造的要塞数量。 接下来的 $k$ 行，每行包含三个整数 $r_i, c_i, z_i$ ($0 \le r_i, c_i, z_i < 2^{20}$)，表示确定第 $i$ 座要塞位置所需的值，以及在拜特雷霆干预时更新 $x$ 的值。

输出格式

输出应包含 $k$ 行，每行包含一个单词 TAK 或 NIE，取决于拜特雷霆是否应该针对新建的要塞进行干预。

样例

样例输入 1

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

样例输出 1

NIE
TAK
NIE
TAK
NIE
TAK
NIE

说明

样例解释：敌国依次在区域 $(0, 1), (1, 0), (1, 3), (2, 2), (0, 4), (2, 3)$ 和 $(2, 1)$ 建造要塞。下图展示了所有要塞，其中被摧毁的要塞带有虚线边框。我们可以看到，最后仍然存在一条便捷的贸易路线。

让我们再看看解码后的坐标是如何得出的。请记住，未被摧毁的要塞不会修改 $x$ 的值。 摧毁第二座要塞不会改变 $x$ 的值，因为 $z_2 = 0$，但之后情况变得更有趣了。 摧毁位于 $(2, 2)$ 的第四座要塞将 $x$ 的值从 $0$ 变为 $16$，因此紧随其后的 $(r_5, c_5) = (2, 3)$ 需要解码为： $$((2 \oplus 16) \bmod n, (3 \oplus 16) \bmod m) = (18 \bmod n, 19 \bmod m) = (0, 4)$$ * 接下来 $(r_6, c_6) = (18, 19)$ 给出了第六座要塞的坐标： $$((18 \oplus 16) \bmod n, (19 \oplus 16) \bmod m) = (2, 3)$$ 这座要塞也必须被摧毁，因此我们将 $x$ 更新为 $x \oplus z_6 = 16 \oplus 17 = 1$。 * 我们使用新的 $x = 1$ 来解码最后一座（第七座）要塞的坐标： $$((3 \oplus 1) \bmod n, (0 \oplus 1) \bmod m) = (2, 1)$$

子任务

在分值为 5 分的测试中，额外满足条件 $n \cdot m \le 25\,000\,000$。