题目描述

比特哈顿镇有 $n\times n$ 个格点，形成了一个网格图。一开始整张图是完整的。

有 $k$ 次操作，每次会删掉图中的一条边 $(u,v)$，你需要回答在删除这条边之后 $u$ 和 $v$ 是否仍然连通。

输入格式

第一行包含两个正整数 $n,k(2\leq n\leq 1500,1\leq k\leq 2n(n-1))$，表示网格图的大小以及操作的个数。

接下来 $k$ 行，每行包含两条信息，每条信息包含两个正整数 $a,b(1\leq a,b\leq n)$ 以及一个字符 $c$（$c$ 为 N 或者 E）。

如果 $c$ 为 N，表示删除 $(a,b)$ 到 $(a,b+1)$ 这条边；如果 $c$ 为 E，表示删除 $(a,b)$ 到 $(a+1,b)$ 这条边。

数据进行了加密，对于每个操作，如果上一个询问回答为 TAK 或者这是第一个操作，那么只考虑第一条信息，否则只考虑第二条信息。数据保证每条边最多被删除一次。

输出格式

输出 $k$ 行，对于每个询问，如果仍然连通，输出 TAK，否则输出 NIE。

3 4
2 1 E 1 2 N
2 1 N 1 1 N
3 1 N 2 1 N
2 2 N 1 1 N

TAK
TAK
NIE
NIE

提示

数据保证，$2\leq n\leq 1500$，$1\leq k\leq 2n(n-1)$，$1\leq a,b\leq n$。