Bytehattan

Bytehattan is one of the islands in the capital of Byteland. Parades, outings and processions are held there so often that streets close and traffic jams up badly. Byteasar, who works at the town hall, has been put in charge of watching the island's traffic.

The streets of Bytehattan form a regular $n \times n$ grid. Read the map as grid coordinates. For every pair of integers $x, y$ with $1 \le x, y \le n$ there is an intersection at the point $(x, y)$, and every two intersections at distance 1 are joined by a street of length 1.

Messages about street closures keep arriving. One message means that one street closes from now on. Once Byteasar learns that a street has closed, he has to decide whether the two intersections at its ends can still be reached from each other along streets that are not closed yet. Write a program that helps him.

The first line contains two integers $n$ and $k$ ($2 \le n \le 1500$, $1 \le k \le 2n(n-1)$). Here $n$ is the number of intersections along one side of the grid and $k$ is the number of closure messages. Each of the next $k$ lines gives the closure information for one street, in chronological order. Each of those lines lists two streets one after the other, but exactly one of them actually closes. If the two intersections at the ends of the street closed in the previous line could still be reached from each other, the first of the two streets closes. If they could not, the second one closes. The first of the $k$ closures applies to the first of the two streets on its line. No street closes twice.

A single street is written as an integer pair $a_i$, $b_i$ ($1 \le a_i, b_i \le n$) followed by a letter $c_i$ ($c_i \in \{N, E\}$). One end of that street is the intersection at $(a_i, b_i)$. If $c_i = N$, the other end is the intersection at $(a_i, b_i + 1)$. If $c_i = E$, the other end is the intersection at $(a_i + 1, b_i)$. If $c_i = N$ then $b_i < n$, and if $c_i = E$ then $a_i < n$.

The jury picked this unusual input format on purpose, to force each closure to be processed before the next one is read.

Print exactly $k$ lines. If the two intersections at the ends of the street closed by the $i$-th message can still be reached from each other afterwards, print TAK (Polish for yes) on the $i$-th line. Otherwise print NIE (Polish for no) on the $i$-th line.