Thanks to the revolutionary discoveries of Professor Bajtazar regarding quantum-byte mechanics and the engineering ideas of Bajton Musk, the galaxy of Bytotia has become the first place in the observable universe where space-time tunnels have begun to be built.

Each tunnel leads from one planet to another (it is one-way). If we enter a tunnel on the starting planet $a$ at time $t$, we will exit on the destination planet $b$ at time $t + c$. The most revolutionary aspect of the whole idea is that $c$ can not only be quite small (allowing travel over long distances in a short time), but also negative (meaning we can arrive at the destination planet earlier than we departed from the starting planet).

The Galactic Government of Bytotia is very concerned about these discoveries, as it fears they could be used to build a time machine, i.e., to enable traveling back in time to the same place, which is not only contrary to common sense but also threatens the safety of the entire galaxy. Therefore, it is necessary to constantly monitor the tunnel system for the creation of a time machine. In other words, after each operation of building or destroying a tunnel, it must be determined whether there exists a sequence of tunnels that starts and ends at the same planet and allows one to be at that planet before departing from it.

Input

The first line of input contains two integers $n$ and $q$, representing the number of planets in the galaxy and the number of queries. The planets are numbered from $1$ to $n$.

The next $q$ lines describe the queries; the $i$-th line contains a query of one of two types: $B \ a \ b \ c$ – a proposal to build a tunnel from planet $a$ to planet $b$ with travel time $c$ ($1 \le a, b \le n$, $-10^5 \le c \le 10^5$); $Z \ j$ – a proposal to destroy the tunnel that was built in the $j$-th query ($1 \le j < i$).

Output

Your program should output $q$ lines; the $i$-th line should contain the word TAK or NIE, depending on whether, after executing all proposals from the first to the $i$-th (inclusive), it is possible to form a time machine from the built tunnels.

Examples

Input 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

Output 1

NIE
NIE
NIE
TAK
NIE
TAK

Subtasks

The test set is divided into the following subtasks. The tests for each subtask consist of one or more separate test groups. In all subtasks, $2 \le n \le 2000$ and $1 \le q \le 4000$.