#3224. 「PA 2019」Osady i warownie 2

内存限制:512 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

题目译自 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 行,每行一个单词 TAKNIE,表示对这 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

样例说明

oiw.png

数据范围与提示

对于所有数据, 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