BZPRO
#5549. [PA2019]Osady i warownie 2
内存限制：512 MiB
时间限制：60 Sec
提交
提交记录
讨论
题目描述
n*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 xor v)%n,y=(c xor v)%m：
1. 如果(x,y)是障碍格，那么忽略这次操作，输出NIE。
2. 否则如果将(x,y)变成障碍格后仍然存在合法路径，那么将(x,y)变成障碍格，输出NIE。
3. 否则如果将(x,y)变成障碍格后不存在合法路径，那么输出TAK，并将v修改为v xor z。
输入格式
第一行三个正整数n,m,k(2<=n,m<=100000,1<=k<=1000000)。
接下来k行，每行三个非负整数r,c,z(0<=r,c,z<2^20)。
输出格式
对于每个操作输出一行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
数据范围与提示
BZPRO