Epidemic

Byteland has just shut its borders. The reason is a new strain of bytebacterium detected in the neighbouring countries. Research shows that the new strain is highly contagious and does not trigger any response from the Bytelanders' immune systems. Once a person is infected, that person stays infected for life (or at least until an effective cure is discovered) and keeps infecting others.

To contain the spread, the Bytelandish government introduced far-reaching restrictions and launched the National Invigilation System, which monitors all social interactions in the country. The government announced that the restrictions will be lifted only when it is certain that nobody, except people under quarantine, is infected. You are the data science expert in charge of analyzing the system's data and determining when the restrictions can be lifted.

There are $n$ people in Byteland. At the start, any one of them may be healthy or infected. After the borders close, $k$ events take place one after another.

A social contact means a group of people meets. If any of them is infected, all of them become infected and stay infected. This is the only way to catch the disease. Touching infected surfaces cannot spread it.

A negative test means a given person takes a test and gets a negative result.

A positive test means a given person takes a test and gets a positive result. That person is immediately put under quarantine and takes part in no social contacts from then on. A later test may still be performed on them. The author has sent an enquiry to the Ministry of Health about why anyone would test a person whose result is already known to be positive, but the ministry's reply has been delayed by three months because of the complex nature of the case.

A query means the health minister asks whether the restrictions can be abolished. In other words, can the information gathered so far prove that nobody except the quarantined people can be infected? If someone might still be infected, you must name such a person, following the guidelines in the Output section.

Your solution must be an online algorithm. You must answer each query right after reading it, without reading any later part of the input.

Correct interpretation of the input depends on the current value of the variable $shift$. At the beginning of each test case, $shift$ is 0. Its later values depend on your program's answers.

The decoding function is defined as decode(p) = ((p - 1 + shift) mod n) + 1, where $1 \le p \le n$.

The first line contains the number of test cases $z$ ($1 \le z \le 1000$). Each test case starts with two integers $n$ and $k$ ($1 \le n \le 500000$, $1 \le k \le 1000000$), where $n$ is the number of people and $k$ is the number of events. People are numbered from 1 to $n$.

The next $k$ lines describe the events in one of the following forms.

K c p_1 ... p_c ($2 \le c \le n$) is a social contact of $c$ people with identifiers decode(p_1), ..., decode(p_c). The $p_i$ are distinct.

N p means person decode(p) takes a test with a negative result.

P p means person decode(p) takes a test with a positive result. This person is quarantined from that moment on, and any later test on this person gives a positive result.

Q p is the ministry's inquiry with starting value decode(p).

The sums of $n$ and $k$ over all test cases do not exceed 500000 and 1000000. The sum of $c$ over all queries does not exceed 1000000.

For each query (type Q), print one line.

If it can be proven that nobody except the quarantined people can be infected, print TAK. The variable $shift$ then becomes 0.

Otherwise, print NIE followed by one integer. Let $s$ be the starting value decode(p). The integer is the identifier of the first person in the sequence $s, s+1, ..., n, 1, 2, ..., s-1$ who might still be infected and is not quarantined. This number becomes the new value of $shift$.

The shift does not change on events of type K, N, or P. For each test case, the positive and negative results always describe a consistent scenario, meaning at least one set of initially infected people makes the events free of contradictions.