Bytehattan 是 Byteland 首府中的岛屿之一。这座岛屿经常举办游行、郊游和列队行进活动。事实上，这些活动非常频繁，导致街道封闭和严重的交通拥堵。在市政厅工作的 Byteasar 被任命负责监控城市交通。

Bytehattan 的街道构成了一个规则的 $n \times n$ 网格。让我们将 Bytehattan 的地图看作网格坐标：对于每一对整数 $x, y$，满足 $1 \le x, y \le n$，在坐标 $(x, y)$ 定义的点处有一个交叉路口。每两个距离为 1 个单位的交叉路口由一条长度为 1 个单位的街道连接。

Byteasar 会收到有关街道封闭的消息。每条消息都通知某条特定的街道将从现在起被封闭。在收到有关某条街道封闭的信息后，Byteasar 需要确定是否仍然可以通过尚未封闭的道路，在位于该封闭街道两端的两个交叉路口之间通行。请帮助他编写一个程序来完成这项工作。

输入格式

输入的第一行包含两个整数 $n$ 和 $k$ ($2 \le n \le 1500, 1 \le k \le 2n(n-1)$ )：Bytehattan 的街道数量和有关封闭街道的消息数量。接下来的 $k$ 行中的每一行都包含有关其中一条街道封闭的信息，信息按时间顺序提供。每一行包含两条描述的街道，一条接一条。实际上，其中恰好有一条街道会被封闭*。如果仍然可以在上一行描述的封闭街道的两端交叉路口之间通行，则这两条街道中的第一条被封闭。如果无法通行，则第二条被封闭。在输入描述的这些封闭操作中，第一次封闭操作应用于所列出的两条街道中的第一条。每条街道只能被封闭一次。

给定街道的描述是一个整数对 $a_i, b_i$ ($1 \le a_i, b_i \le n$)，后跟一个字母 $c_i$ ($c_i \in \{\text{N, E}\}$)。这样的三元组确定了一条街道，其一端位于坐标为 $(a_i, b_i)$ 的交叉路口。如果 $c_i = \text{N}$，则街道的另一端位于坐标为 $(a_i, b_i+1)$ 的交叉路口。如果 $c_i = \text{E}$，则街道的另一端位于坐标为 $(a_i+1, b_i)$ 的交叉路口。如果 $c_i = \text{N}$，则 $b_i < n$，同样如果 $c_i = \text{E}$，则 $a_i < n$。

输出格式

输出应恰好包含 $k$ 行。如果在第 $i$ 次街道封闭后，仍然可以在输入中该封闭街道的两端交叉路口之间通行，则在输出的第 $i$ 行应包含单词 TAK（波兰语中的“是”）。否则，第 $i$ 行应包含单词 NIE（波兰语中的“否”）。

样例

样例输入 1

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

样例输出 1

TAK
TAK
NIE
NIE

说明

*评委的意图是，这种非典型的输入格式会产生在处理后续街道封闭之前先处理每次街道封闭的需求。