P10665 [AMPPZ2013] Bytehattan

比特哈顿镇有 $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。

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