题目描述

题目译自 XXVII Olimpiada Informatyczna – Eliminacje do IOI Tunele czasoprzestrzenne

由于 Bajtazar 教授在量子拜托力学方面的革命性发现以及 Bajton Musk 的工程创新，拜托西亚星系成为可观测宇宙中首个开始建造时空隧道的地方。

每个隧道从一个星球通往另一个星球（单向的）。如果我们在时间 $t$ 从起点星球 $a$ 进入隧道，那么我们将在时间 $t+c$ 到达目标星球 $b$。这一想法中最具革命性的是，$c$ 不仅可以非常小（即允许在短时间内进行长距离旅行），甚至可以是负数（即在目标星球的时间可能早于从起点星球出发的时间）。

拜托西亚星系政府对此深感担忧，他们担心这些发现可能被用来建造时间机器，即允许回到过去的时间点，这不仅违背常识，还威胁到整个星系的安全。因此，必须持续监控隧道系统，以防止时间机器的出现。换句话说，每次建造或摧毁隧道后，都需要判断是否存在一系列隧道，从某个星球出发并回到该星球，且回到时的时间早于出发时间。

输入格式

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

接下来的 $q$ 行描述查询；第 $i$ 行包含以下两种查询之一：

• $\texttt{B}\ a\ b\ c$：提议建造一条从星球 $a$ 到星球 $b$ 的隧道，旅行时间为 $c$ $(1 \leq a, b \leq n, -10^{5} \leq c \leq 10^{5})$；
• $\texttt{Z}\ j$：提议摧毁在第 $j$ $(1 \leq j \leq i)$ 次查询中建造的隧道 。

输出格式

你的程序应输出 $q$ 行；第 $i$ 行应为 TAK 或 NIE，表示在执行从第一次到第 $i$ 次（包含第 $i$ 次）所有提议后，是否可以通过已建造的隧道构建时间机器。

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

NIE
NIE
NIE
TAK
NIE
TAK

附加样例

1. $n=10$，$q=20$，建造的（并立即摧毁）仅为循环，即每次 B 类型查询中 $a=b$；
2. $n=300$，$q=300$，只有 $\texttt{B}$ 类型查询，始终 $c=-1$，构建包含所有星球的循环；
3. $n=1000$，$q=3000$，构建如第二个样例的循环。完成后添加 $500$ 个随机隧道，然后按逆序摧毁所有隧道。

数据范围与提示

在所有子任务中，均满足 $2 \leq n \leq 2000$ 且 $1 \leq q \leq 4000$。详细子任务附加限制及分值如下表所示。