得益于 Bajtazar 教授在量子字节力学方面的革命性发现以及 Bajton Musk 的工程构想，Bajtocja 星系成为了可观测宇宙中第一个开始建造时空隧道的地方。

每条隧道都从一颗行星通往另一颗行星（单向）。如果我们从起始行星 $a$ 在时间 $t$ 进入隧道，我们将会在时间 $t + c$ 到达目标行星 $b$。整个构想中最具革命性的地方在于，$c$ 不仅可以非常小（从而实现短时间内长距离旅行），还可以是负数（即我们可以在目标行星上比从起始行星出发时更早到达）。

Bajtocja 星系政府对这些发现感到非常担忧，因为他们担心这些发现可能被用于制造时间机器，即允许回到过去到达同一个地点，这不仅违背常识，还威胁到整个星系的安全。因此，必须持续监控隧道系统，以防出现时间机器。换句话说，在每次建造或摧毁隧道的操作后，都需要确定是否存在一个隧道序列，它从某颗行星出发并回到该行星，且能使我们在出发前就到达该行星。

输入格式

输入的第一行包含两个整数 $n$ 和 $q$，分别表示星系中的行星数量和查询数量。行星编号从 $1$ 到 $n$。

接下来的 $q$ 行描述查询；第 $i$ 行包含以下两种查询之一： B a b c – 提议建造一条从行星 $a$ 到行星 $b$、旅行时间为 $c$ 的隧道（$1 \le a, b \le n, -10^5 \le c \le 10^5$）； Z j – 提议摧毁在第 $j$ 次查询中建造的隧道（$1 \le j < i$）。

输出格式

你的程序应输出 $q$ 行；第 $i$ 行应包含单词 TAK 或 NIE，具体取决于在执行从第一次到第 $i$ 次（含）的所有提议后，是否可以利用已建成的隧道构建出时间机器。

样例

输入 1

4 6
B 1 2 3
B 3 1 -4
B 2 3 2
B 2 3 0
Z 1
B 1 3 3

输出 1

NIE
NIE
NIE
TAK
NIE
TAK

子任务

测试集分为以下子任务。对于每个子任务，测试用例由一组或多组独立的测试数据组成。在所有子任务中，满足 $2 \le n \le 2000$ 且 $1 \le q \le 4000$。