Byteland щойно закрив кордони через новий штам bytebacterium, виявлений у сусідніх країнах. Дослідження показують, що новий штам не лише надзвичайно заразний, а й не викликає жодної реакції імунної системи жителів Byteland. Тому кожна інфікована людина залишатиметься такою та продовжуватиме заражати інших усе життя (або принаймні до відкриття ефективних ліків).

Щоб стримати поширення bytebacterium, уряд Byteland запровадив масштабні обмеження та запустив Національну систему стеження, яка дає змогу відстежувати всі соціальні взаємодії в країні. Було оголошено, що обмеження скасують лише тоді, коли стане відомо напевно, що ніхто, крім ізольованих людей, не інфікований bytebacterium. Як найвідомішому в країні фахівцю з науки про дані, вам доручили аналізувати дані системи стеження та визначити, коли обмеження справді можна скасувати.

У Byteland мешкає $n$ людей, і спочатку кожен із них може бути здоровим або інфікованим bytebacterium. Після закриття кордонів одна за одною відбуваються $k$ подій таких типів:

• Із системи стеження ви дізнаєтеся, що певна група людей зустрілася. Якщо хтось із них інфікований, усі вони також стають інфікованими й залишаються такими назавжди. Такий соціальний контакт є єдиним можливим способом заразитися (усупереч першим повідомленням преси, захворіти через дотик до заражених поверхонь насправді неможливо).

• Певна людина проходить тест на bytebacterium та отримує негативний результат.

• Певна людина проходить тест на bytebacterium та отримує позитивний результат. Її негайно ізолюють, і відтоді вона більше не бере участі в соціальних контактах (хоча згодом їй усе ще можуть зробити ще один тест [1]).

• Ви отримуєте запит від міністра охорони здоров’я: чи можна вже скасувати обмеження, тобто чи дає вся отримана дотепер інформація змогу довести, що ніхто, крім ізольованих людей, не може бути інфікованим. Якщо хтось усе ще може бути інфікованим, потрібно навести приклад такої людини відповідно до вказівок міністерства, описаних у розділі «Вихідні дані».

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

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

Вхідні дані

Правильне тлумачення вхідних даних залежить від поточного значення змінної $\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 мають іти до кінця цього тестового випадку.