Byteland acaba de fechar suas fronteiras devido a uma nova cepa de bytebacterium detectada nos países vizinhos. Pesquisas mostram que a nova cepa não só é altamente contagiosa, como também não provoca nenhuma resposta do sistema imunológico dos habitantes de Byteland, de modo que uma pessoa, uma vez infectada, permanecerá assim — e continuará infectando outras — por toda a vida (ou, pelo menos, até que uma cura eficaz seja descoberta).

Para conter a propagação de bytebacterium, o governo de Byteland introduziu restrições abrangentes e lançou o Sistema Nacional de Vigilância, que permite monitorar todas as interações sociais no país. Foi anunciado que as restrições só serão suspensas quando houver certeza de que ninguém, exceto as pessoas colocadas em quarentena, está infectado com bytebacterium. Como o mais renomado especialista em ciência de dados do país, você recebeu a tarefa de analisar os dados do sistema de vigilância e determinar quando as restrições podem de fato ser suspensas.

Há $n$ pessoas em Byteland e, inicialmente, cada uma delas pode estar saudável ou infectada com bytebacterium. Após o fechamento das fronteiras, ocorrem, um após o outro, $k$ eventos dos seguintes tipos:

• Você descobre pelo sistema de vigilância que um grupo de pessoas se reúne. Se alguma delas estiver infectada, todas também ficam infectadas (e permanecerão assim indefinidamente). Esse tipo de contato social é a única forma possível de contrair a doença (ao contrário das notícias iniciais da imprensa, na verdade é impossível adoecer por tocar em superfícies infectadas).

• Uma determinada pessoa faz um teste de bytebacterium e recebe um resultado negativo.

• Uma determinada pessoa faz um teste de bytebacterium e recebe um resultado positivo. Essa pessoa é imediatamente colocada em quarentena e não participará de nenhum contato social a partir desse momento (embora possa acontecer de outro teste ainda ser realizado nela mais tarde [1]).

• Você recebe uma consulta do ministro da saúde para determinar se as restrições já podem ser abolidas, isto é, se todas as informações obtidas até então permitem provar que ninguém, exceto as pessoas em quarentena, pode estar infectado. Se ainda for possível que algum indivíduo esteja infectado, você deve dar um exemplo de tal pessoa, de acordo com as diretrizes do ministério (descritas na seção Saída).

Sua solução deve implementar um algoritmo online: você precisa ser capaz de responder a cada consulta imediatamente após recebê-la, sem ler nenhuma parte posterior da entrada.

[1] Você pode se perguntar por que alguém faria um teste de bytebacterium em uma pessoa assim, quando é claro que seu resultado deve ser positivo. O autor deste problema enviou uma consulta a esse respeito ao Ministério da Saúde de Byteland, mas foi informado de que o prazo legal de resposta havia sido prorrogado por três meses devido à natureza complexa do caso.

Entrada

A interpretação correta dos dados de entrada dependerá do valor atual da variável $\mathit{shift}$. No início de cada caso de teste, a variável $\mathit{shift}$ é inicializada com $0$, enquanto seus valores posteriores dependerão das respostas retornadas pelo seu programa. Esse formato de entrada tem o objetivo de garantir que sua implementação responda a cada consulta imediatamente após lê-la.

A função de decodificação é definida da seguinte forma:

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

Aqui, $p$ é um inteiro que satisfaz $1 \le p \le n$, e $\bmod$ é a operação de obter o resto da divisão inteira.

A primeira linha da entrada contém o número de casos de teste $z$ ($1 \le z \le 1\,000$). Seguem-se as descrições dos casos de teste.

A primeira linha contém dois inteiros $n$ e $k$ ($1 \le n \le 500\,000$, $1 \le k \le 1\,000\,000$), indicando o número de pessoas e o número de eventos, respectivamente. As pessoas são numeradas de $1$ a $n$.

As próximas $k$ linhas descrevem os eventos consecutivos, cada um em uma das seguintes formas:

• A letra K e um inteiro $c$ ($2 \le c \le n$), seguidos por $c$ inteiros distintos $p_1,\ldots,p_c$ ($1 \le p_i \le n$): um contato social do qual participam $c$ pessoas com identificadores $\operatorname{decode}(p_1),\ldots,\operatorname{decode}(p_c)$.

• A letra N seguida por um inteiro $p$ ($1 \le p \le n$): a pessoa de número $\operatorname{decode}(p)$ faz um teste de bytebacterium que dá resultado negativo.

• A letra P seguida por um inteiro $p$ ($1 \le p \le n$): a pessoa de número $\operatorname{decode}(p)$ faz um teste de bytebacterium que dá resultado positivo. Essa pessoa é imediatamente colocada em quarentena e não participará de nenhum contato social a partir desse momento (e qualquer teste posterior realizado nela inevitavelmente também dará resultado positivo).

• A letra Q seguida por um inteiro $p$ ($1 \le p \le n$): a consulta do ministério com valor inicial (veja a seção Saída) igual a $\operatorname{decode}(p)$.

As somas dos valores de $n$ e $k$ em todos os casos de teste não excedem $500\,000$ e $1\,000\,000$, respectivamente. A soma dos valores de $c$ em todas as consultas de todos os casos de teste não excede $1\,000\,000$.

Saída

Para cada caso de teste, imprima uma linha para cada consulta (evento do tipo Q) que apareça nesse caso de teste.

Se, no momento da $i$-ésima consulta, for possível provar que é impossível alguém (exceto as pessoas em quarentena) estar infectado, a $i$-ésima linha deve conter a palavra TAK [2]. Nesse caso, a variável $\mathit{shift}$ muda seu valor para $0$.

Caso contrário, a $i$-ésima linha deve conter a palavra NIE seguida por um único inteiro. Se $\operatorname{decode}(p)$ for o valor inicial da consulta, o inteiro deve ser o identificador da primeira pessoa na sequência $(\operatorname{decode}(p),\operatorname{decode}(p)+1,\ldots,n,1,2,\ldots,\operatorname{decode}(p)-1)$ que possa estar infectada com bytebacterium, mas não esteja em quarentena. Esse número se torna o novo valor da variável $\mathit{shift}$.

[2] Pode acontecer de, em algum momento, todos os habitantes de Byteland estarem em quarentena. É claro que, nesse caso, essa afirmação se torna trivialmente verdadeira e seu programa deve imprimir TAK.

Observações

• A variável $\mathit{shift}$ não muda seu valor nos eventos dos tipos K, N ou P.

• Os resultados positivos e negativos dos testes sempre descrevem um cenário possível. Isto é, para cada caso de teste existe pelo menos um conjunto de pessoas inicialmente infectadas para o qual a sequência de eventos descrita na entrada não contém nenhuma contradição.

Exemplos

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

Saída 1

NIE 5
NIE 1
TAK
TAK

• Após a decodificação, a entrada mostrada acima fica da seguinte forma:

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

Explicação

• Antes da primeira consulta, as pessoas 3, 4 e 5 se encontram, depois as pessoas 5 e 6 se encontram e, em seguida, a pessoa 3 recebe um resultado negativo em um teste. Ao receber a primeira consulta, podemos, usando todas as informações coletadas até então, chegar às seguintes conclusões (começando pelo valor inicial da consulta, 3). A pessoa 3 deve estar saudável (ela acabou de receber um resultado negativo em um teste). A pessoa 4 também deve estar saudável (ela não poderia estar infectada no momento do primeiro encontro, pois, caso contrário, teria infectado as pessoas 3 e 5, o que contradiz o resultado negativo obtido mais tarde pela pessoa 3; desde então, a pessoa 4 não teve nenhuma possibilidade de se infectar, logo deve estar saudável no momento). A pessoa 5 pode estar infectada (ela devia estar saudável quando se encontrou com 3 e 4, mas depois se encontrou com a pessoa 6, cujo estado de saúde não pode ser deduzido das informações disponíveis). Portanto, a resposta é NIE 5 e $\mathit{shift}$ muda seu valor para $5$.

• Após a primeira consulta, a pessoa 6 recebe um resultado positivo em um teste, depois as pessoas 1 e 5 se encontram e, em seguida, a pessoa 5 recebe um resultado positivo em um teste. Ao receber a segunda consulta, podemos, usando todas as informações coletadas até então, chegar às seguintes conclusões (começando pelo valor inicial da consulta, 3). As pessoas 3 e 4 devem estar saudáveis. As pessoas 5 e 6 estão em quarentena. A pessoa 1 pode estar infectada (na verdade, podemos até ter certeza de que ela deve estar infectada, mas seu programa não precisa distinguir entre esses dois casos). Portanto, a resposta é NIE 1 e $\mathit{shift}$ muda seu valor para $1$.

• Em seguida, a pessoa 1 recebe um resultado positivo em um teste, depois as pessoas 2 e 4 se encontram e, então, a pessoa 4 recebe um resultado negativo em um teste. Ao receber a segunda consulta, podemos chegar às seguintes conclusões (começando pelo valor inicial 5). As pessoas 5, 6 e 1 estão em quarentena. A pessoa 2 deve estar saudável devido ao resultado negativo obtido pela pessoa 4. As pessoas 3 e 4 também devem estar saudáveis. Portanto, a resposta é TAK, pois é possível provar que todas as pessoas fora da quarentena (2, 3 e 4) devem estar saudáveis. A variável $\mathit{shift}$ muda seu valor para $0$.

• Após a terceira consulta, a pessoa 2 recebe um resultado negativo em um teste. Como você pode observar facilmente, essa parte da entrada é de fato irrelevante: após a primeira resposta TAK, devem se seguir respostas TAK até o fim desse caso de teste.