Byteland только что закрыл свои границы: в соседних странах обнаружен новый штамм bytebacterium. Исследования показывают, что новый штамм не только крайне заразен, но и не вызывает никакой реакции иммунной системы жителей Byteland, поэтому однажды заразившийся человек останется заражённым и будет продолжать заражать других всю жизнь (или, по крайней мере, до открытия эффективного лекарства).

Чтобы сдержать распространение bytebacterium, правительство Byteland ввело масштабные ограничения и запустило National Invigilation System, позволяющую отслеживать все социальные взаимодействия в стране. Было объявлено, что ограничения снимут лишь тогда, когда станет достоверно известно, что никто, кроме помещённых на карантин людей, не заражён bytebacterium. Вам, самому известному специалисту страны по анализу данных, поручили проанализировать данные системы наблюдения и определить, когда ограничения действительно можно снять.

В Byteland живут $n$ человек, и изначально каждый из них может быть как здоров, так и заражён bytebacterium. После закрытия границ одно за другим происходят $k$ событий следующих типов:

• Из системы наблюдения вы узнаёте, что некоторая группа людей встречается. Если хотя бы один из них заражён, все остальные тоже заражаются (и остаются заражёнными неограниченно долго). Такие социальные контакты — единственный возможный способ заразиться (вопреки первоначальным сообщениям прессы, заболеть из-за прикосновения к заражённым поверхностям на самом деле невозможно).

• Некоторый человек проходит тест на bytebacterium и получает отрицательный результат.

• Некоторый человек проходит тест на bytebacterium и получает положительный результат. Его немедленно помещают на карантин, и с этого момента он больше не участвует ни в каких социальных контактах (хотя позже его всё же могут протестировать снова [1]).

• Вы получаете запрос от министра здравоохранения: можно ли уже отменить ограничения, то есть позволяет ли вся полученная к этому моменту информация доказать, что никто, кроме людей на карантине, не может быть заражён. Если хотя бы один человек всё ещё может быть заражён, нужно привести пример такого человека в соответствии с указаниями министерства (описанными в разделе «Выходные данные»).

Ваше решение должно реализовывать онлайн-алгоритм: вы должны отвечать на каждый запрос сразу после его получения, не читая последующие части входных данных.

[1] Вы можете задаться вопросом, зачем кому-либо тестировать такого человека на bytebacterium, если очевидно, что результат обязательно будет положительным. Автор задачи направил соответствующий запрос в министерство здравоохранения Byteland, но получил уведомление, что установленный законом срок ответа продлён на три месяца из-за сложности рассматриваемого дела.

Входные данные

Правильная интерпретация входных данных зависит от текущего значения переменной $\mathit{shift}$. В начале каждого набора тестовых данных $\mathit{shift}$ инициализируется значением $0$, а её последующие значения зависят от ответов вашей программы. Такой формат входных данных предназначен для того, чтобы ваша реализация отвечала на каждый запрос сразу после его чтения.

Функция декодирования определяется следующим образом:

$$\operatorname{decode}(p)=((p-1+\mathit{shift})\bmod n)+1.$$

Здесь $p$ — целое число, удовлетворяющее $1\le p\le n$, а $\bmod$ — операция взятия остатка от целочисленного деления.

Первая строка входных данных содержит количество наборов тестовых данных $z$ ($1\le z\le 1\,000$). Далее следуют описания наборов.

Первая строка содержит два целых числа $n$ и $k$ ($1\le n\le 500\,000$, $1\le k\le 1\,000\,000$), обозначающих соответственно количество людей и количество событий. Люди пронумерованы от $1$ до $n$.

Следующие $k$ строк описывают последовательные события, каждое в одной из следующих форм:

• Буква K и целое число $c$ ($2\le c\le n$), затем $c$ различных целых чисел $p_1,\ldots,p_c$ ($1\le p_i\le n$) — социальный контакт, в котором участвуют $c$ человек с номерами $\operatorname{decode}(p_1),\ldots,\operatorname{decode}(p_c)$.

• Буква N, затем целое число $p$ ($1\le p\le n$) — человек с номером $\operatorname{decode}(p)$ проходит тест на bytebacterium с отрицательным результатом.

• Буква P, затем целое число $p$ ($1\le p\le n$) — человек с номером $\operatorname{decode}(p)$ проходит тест на bytebacterium с положительным результатом. Его немедленно помещают на карантин, и с этого момента он больше не участвует в социальных контактах (при этом любой его последующий тест неизбежно тоже даст положительный результат).

• Буква Q, затем целое число $p$ ($1\le p\le n$) — запрос министерства с начальным значением (см. раздел «Выходные данные»), равным $\operatorname{decode}(p)$.

Суммы значений $n$ и $k$ по всем наборам тестовых данных не превышают $500\,000$ и $1\,000\,000$ соответственно. Сумма значений $c$ по всем запросам всех наборов не превышает $1\,000\,000$.

Выходные данные

Для каждого набора тестовых данных выведите по одной строке на каждый встречающийся в нём запрос (событие типа Q).

Если в момент $i$-го запроса можно доказать, что никто, кроме людей на карантине, не может быть заражён, $i$-я строка должна содержать слово TAK [2]. В этом случае значение переменной $\mathit{shift}$ меняется на $0$.

Иначе $i$-я строка должна содержать слово NIE, а затем одно целое число. Если начальное значение запроса равно $\operatorname{decode}(p)$, это число должно быть номером первого человека в последовательности $(\operatorname{decode}(p),\operatorname{decode}(p)+1,\ldots,n,1,2,\ldots,\operatorname{decode}(p)-1)$, который может быть заражён bytebacterium, но не находится на карантине. Это число становится новым значением переменной $\mathit{shift}$.

[2] Может случиться, что в некоторый момент все жители Byteland находятся на карантине. Разумеется, в этом случае утверждение тривиально истинно, и ваша программа должна вывести «TAK».

Примечание

• Значение переменной $\mathit{shift}$ не меняется при событиях типов K, N и P.

• Положительные и отрицательные результаты тестов всегда описывают возможный сценарий. То есть для каждого набора тестовых данных существует хотя бы одно множество изначально заражённых людей, для которого описанная во входных данных последовательность событий не содержит противоречий.

Примеры

Входные данные 1

1
6 14
K 3 3 4 5
K 2 6 5
N 3
Q 3
P 1
K 2 6 2
P 6
Q 4
P 6
K 2 1 3
N 3
Q 4
N 2
Q 1

Выходные данные 1

NIE 5
NIE 1
TAK
TAK

• После декодирования приведённые выше входные данные выглядят следующим образом:

1
6 14
K 3 3 4 5
K 2 6 5
N 3
Q 3
P 6
K 2 5 1
P 5
Q 3
P 1
K 2 2 4
N 4
Q 5
N 2
Q 1

Примечание

• До первого запроса встречаются люди $3$, $4$ и $5$, затем люди $5$ и $6$, после чего человек $3$ получает отрицательный результат теста. При получении первого запроса на основе всей собранной к этому моменту информации можно сделать следующие выводы (начиная с начального значения запроса $3$). Человек $3$ обязательно здоров (он только что получил отрицательный результат теста). Человек $4$ тоже обязательно здоров (она не могла быть заражена при первой встрече, иначе заразила бы людей $3$ и $5$, что противоречило бы отрицательному результату теста, позже полученному человеком $3$; с тех пор у человека $4$ не было возможности заразиться, так что сейчас она обязательно здорова). Человек $5$ может быть заражён (он обязательно был здоров при встрече с $3$ и $4$, но позже встретился с человеком $6$, состояние здоровья которого нельзя установить по имеющейся информации). Поэтому ответ — NIE 5, а значение $\mathit{shift}$ меняется на $5$.

• После первого запроса человек $6$ получает положительный результат теста, затем встречаются люди $1$ и $5$, после чего человек $5$ получает положительный результат теста. При получении второго запроса на основе всей собранной к этому моменту информации можно сделать следующие выводы (начиная с начального значения запроса $3$). $3$ и $4$ обязательно здоровы. $5$ и $6$ находятся на карантине. Человек $1$ может быть заражён (на самом деле можно даже быть уверенными, что она обязательно заражена, но вашей программе не нужно различать эти два случая). Поэтому ответ — NIE 1, а значение $\mathit{shift}$ меняется на $1$.

• После этого человек $1$ получает положительный результат теста, затем встречаются люди $2$ и $4$, а потом человек $4$ получает отрицательный результат теста. При получении второго запроса можно сделать следующие выводы (начиная с начального значения $5$). Люди $5$, $6$ и $1$ находятся на карантине. Человек $2$ обязательно здоров вследствие отрицательного результата теста человека $4$. Люди $3$ и $4$ тоже обязательно здоровы. Поэтому ответ — TAK: можно доказать, что все люди вне карантина ($2$, $3$ и $4$) обязательно здоровы. Значение переменной $\mathit{shift}$ меняется на $0$.

• После третьего запроса человек $2$ получает отрицательный результат теста. Как легко заметить, эта часть входных данных фактически несущественна: после первого ответа TAK до конца данного набора тестовых данных обязательно следуют ответы TAK.