Byteland acaba de cerrar sus fronteras debido a una nueva cepa de bytebacterium detectada en los países vecinos. Los estudios muestran que la nueva cepa no solo es muy contagiosa, sino que tampoco provoca ninguna respuesta del sistema inmunitario de los habitantes de Byteland, por lo que una persona infectada seguirá estándolo —y continuará infectando a otras— durante toda su vida (o, al menos, hasta que se descubra una cura eficaz).

Para contener la propagación de bytebacterium, el gobierno de Byteland introdujo amplias restricciones y puso en marcha el Sistema Nacional de Vigilancia, que permite supervisar todas las interacciones sociales del país. Se anunció que las restricciones solo se levantarán cuando se tenga la certeza de que nadie, salvo las personas puestas en cuarentena, está infectado con bytebacterium. Como el experto en ciencia de datos más reconocido del país, se te ha confiado el análisis de los datos del sistema de vigilancia y la determinación de cuándo pueden levantarse realmente las restricciones.

En Byteland hay $n$ personas y, al principio, cualquiera de ellas puede estar sana o infectada con bytebacterium. Tras el cierre de las fronteras, se producen uno tras otro $k$ eventos de los siguientes tipos:

• El sistema de vigilancia te informa de que un grupo de personas se reúne. Si alguna de ellas está infectada, todas quedan también infectadas (y seguirán estándolo indefinidamente). Este tipo de contacto social es la única forma posible de contraer la enfermedad (en contra de los primeros informes de prensa, en realidad es imposible enfermar por tocar superficies infectadas).

• Una persona se hace una prueba de bytebacterium y obtiene un resultado negativo.

• Una persona se hace una prueba de bytebacterium y obtiene un resultado positivo. Esta persona se pone inmediatamente en cuarentena y, desde ese momento, no participa en ningún contacto social (aunque puede ocurrir que más adelante se le haga otra prueba [1]).

• Recibes una consulta del ministro de sanidad para determinar si ya pueden eliminarse las restricciones, es decir, si toda la información obtenida hasta el momento permite demostrar que nadie, salvo las personas en cuarentena, puede estar infectado. Si alguna persona todavía pudiera estar infectada, debes dar un ejemplo de tal persona de acuerdo con las directrices del ministerio (descritas en la sección Salida).

Tu solución debe implementar un algoritmo en línea: debes poder responder a cada consulta inmediatamente después de recibirla, sin leer ninguna parte posterior de la entrada.

[1] Quizá te preguntes por qué alguien haría una prueba de bytebacterium a una persona así, cuando está claro que el resultado debe ser positivo. El autor de este problema dirigió la consulta correspondiente al Ministerio de Sanidad de Byteland, pero recibió la notificación de que el plazo legal de respuesta se había ampliado tres meses debido a la complejidad del asunto.

Entrada

La interpretación correcta de los datos de entrada dependerá del valor actual de la variable $\mathit{shift}$. Al comienzo de cada caso de prueba, la variable $\mathit{shift}$ se inicializa en $0$, mientras que sus valores posteriores dependerán de las respuestas que dé tu programa. Este formato de entrada pretende garantizar que tu implementación responda a cada consulta inmediatamente después de leerla.

La función de decodificación se define así:

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

Aquí, $p$ es un entero que satisface $1 \le p \le n$, y $\bmod$ es la operación de obtener el resto de la división entera.

La primera línea de la entrada contiene el número de casos de prueba $z$ ($1 \le z \le 1\,000$). A continuación se describen los casos de prueba.

La primera línea contiene dos enteros $n$ y $k$ ($1 \le n \le 500\,000$, $1 \le k \le 1\,000\,000$), que indican el número de personas y el número de eventos, respectivamente. Las personas están numeradas de $1$ a $n$.

Las siguientes $k$ líneas describen los eventos consecutivos, cada uno con una de las siguientes formas:

• La letra K y un entero $c$ ($2 \le c \le n$), seguidos de $c$ enteros distintos $p_1,\ldots,p_c$ ($1 \le p_i \le n$): un contacto social en el que participan $c$ personas con identificadores $\operatorname{decode}(p_1),\ldots,\operatorname{decode}(p_c)$.

• La letra N seguida de un entero $p$ ($1 \le p \le n$): la persona número $\operatorname{decode}(p)$ se hace una prueba de bytebacterium que da un resultado negativo.

• La letra P seguida de un entero $p$ ($1 \le p \le n$): la persona número $\operatorname{decode}(p)$ se hace una prueba de bytebacterium que da un resultado positivo. Esta persona se pone inmediatamente en cuarentena y no participa en ningún contacto social a partir de ese momento (y cualquier prueba posterior que se le haga dará también, inevitablemente, un resultado positivo).

• La letra Q seguida de un entero $p$ ($1 \le p \le n$): la consulta del ministerio con un valor inicial (véase la sección Salida) igual a $\operatorname{decode}(p)$.

Las sumas de los valores de $n$ y $k$ sobre todos los casos de prueba no superan $500\,000$ y $1\,000\,000$, respectivamente. La suma de los valores de $c$ sobre todas las consultas de todos los casos de prueba no supera $1\,000\,000$.

Salida

Para cada caso de prueba, imprime una línea por cada consulta (evento de tipo Q) que aparezca en él.

Si, en el momento de la consulta $i$-ésima, puede demostrarse que es imposible que alguien (salvo las personas en cuarentena) esté infectado, la línea $i$-ésima debe contener la palabra TAK [2]. En ese caso, la variable $\mathit{shift}$ cambia su valor a $0$.

En caso contrario, la línea $i$-ésima debe contener la palabra NIE seguida de un entero. Si $\operatorname{decode}(p)$ es el valor inicial de la consulta, el entero debe ser el identificador de la primera persona de la secuencia $(\operatorname{decode}(p),\operatorname{decode}(p)+1,\ldots,n,1,2,\ldots,\operatorname{decode}(p)-1)$ que podría estar infectada con bytebacterium pero no está en cuarentena. Este número pasa a ser el nuevo valor de la variable $\mathit{shift}$.

[2] Puede ocurrir que, en algún momento, todos los habitantes de Byteland estén en cuarentena. Por supuesto, en tal caso esta afirmación se cumple trivialmente y tu programa debe imprimir TAK.

Observaciones

• La variable $\mathit{shift}$ no cambia su valor en los eventos de tipo K, N o P.

• Los resultados positivos y negativos de las pruebas siempre describen un escenario posible. Es decir, para cada caso de prueba existe al menos un conjunto de personas inicialmente infectadas para el que la secuencia de eventos descrita en la entrada no contiene ninguna contradicción.

Ejemplos

Entrada 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

Salida 1

NIE 5
NIE 1
TAK
TAK

• Después de decodificarla, la entrada anterior tiene el siguiente aspecto:

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

Nota

• Antes de la primera consulta, se reúnen las personas 3, 4 y 5; después se reúnen las personas 5 y 6; y después la persona 3 obtiene un resultado negativo en una prueba. Al recibir la primera consulta, podemos, utilizando toda la información recopilada hasta entonces, deducir las siguientes conclusiones (empezando por el valor inicial de la consulta, 3). La persona 3 debe estar sana (acaba de obtener un resultado negativo en una prueba). La persona 4 también debe estar sana (no podía estar infectada en el momento de la primera reunión, porque de lo contrario habría infectado a las personas 3 y 5, lo que contradiría el resultado negativo que obtuvo después la persona 3; desde entonces, la persona 4 no ha tenido ninguna posibilidad de infectarse, por lo que debe estar sana en este momento). La persona 5 podría estar infectada (debía estar sana cuando se reunió con 3 y 4, pero más tarde se reunió con la persona 6, cuyo estado de salud no puede deducirse de la información disponible). Por tanto, la respuesta es NIE 5 y $\mathit{shift}$ cambia su valor a $5$.

• Después de la primera consulta, la persona 6 obtiene un resultado positivo en una prueba; después se reúnen las personas 1 y 5; y después la persona 5 obtiene un resultado positivo en una prueba. Al recibir la segunda consulta, podemos, utilizando toda la información recopilada hasta entonces, deducir las siguientes conclusiones (empezando por el valor inicial de la consulta, 3). Las personas 3 y 4 deben estar sanas. Las personas 5 y 6 están en cuarentena. La persona 1 podría estar infectada (de hecho, podemos incluso estar seguros de que debe estar infectada, pero tu programa no necesita distinguir entre estos dos casos). Por tanto, la respuesta es NIE 1 y $\mathit{shift}$ cambia su valor a $1$.

• Después, la persona 1 obtiene un resultado positivo en una prueba; después se reúnen las personas 2 y 4; y después la persona 4 obtiene un resultado negativo en una prueba. Al recibir la segunda consulta, podemos deducir las siguientes conclusiones (empezando por el valor inicial 5). Las personas 5, 6 y 1 están en cuarentena. La persona 2 debe estar sana debido al resultado negativo obtenido por la persona 4. Las personas 3 y 4 también deben estar sanas. Por tanto, la respuesta es TAK, porque puede demostrarse que todas las personas que no están en cuarentena (2, 3 y 4) deben estar sanas. La variable $\mathit{shift}$ cambia su valor a $0$.

• Después de la tercera consulta, la persona 2 obtiene un resultado negativo en una prueba. Como puedes observar fácilmente, esta parte de la entrada es, de hecho, irrelevante: después de la primera respuesta TAK, deben seguir respuestas TAK hasta el final del caso de prueba.