Problem Description

Bytehattan has $n \times n$ grid points, forming a grid graph. At the beginning, the whole graph is complete.

There are $k$ operations. In each operation, an edge $(u,v)$ in the graph is deleted. You need to answer whether $u$ and $v$ are still connected after deleting this edge.

Input Format

The first line contains two positive integers $n,k(2\leq n\leq 1500,1\leq k\leq 2n(n-1))$, representing the size of the grid graph and the number of operations.

The next $k$ lines describe the operations. Each line contains two pieces of information. Each piece of information contains two positive integers $a,b(1\leq a,b\leq n)$ and a character $c$ ($c$ is N or E).

If $c$ is N, it means deleting the edge from $(a,b)$ to $(a,b+1)$. If $c$ is E, it means deleting the edge from $(a,b)$ to $(a+1,b)$.

The data is encrypted. For each operation, if the previous answer was TAK or this is the first operation, only consider the first piece of information; otherwise, only consider the second piece of information. The data guarantees that each edge is deleted at most once.

Output Format

Output $k$ lines. For each query, if the two endpoints are still connected, output TAK; otherwise output 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

Hint

Constraints: $2\leq n\leq 1500$, $1\leq k\leq 2n(n-1)$, $1\leq a,b\leq n$.

Translated by ChatGPT 5