Byteland vient de fermer ses frontières, car une nouvelle souche de bytebacterium a été détectée dans les pays voisins. Les recherches montrent que cette souche est non seulement très contagieuse, mais ne déclenche aucune réaction du système immunitaire des habitants de Byteland. Toute personne infectée le reste donc, et continue à infecter les autres, toute sa vie (ou, au moins, jusqu’à la découverte d’un traitement efficace).

Pour contenir la propagation du bytebacterium, le gouvernement de Byteland a instauré de vastes restrictions et lancé le Système national de surveillance, qui permet de surveiller toutes les interactions sociales du pays. Il a annoncé que les restrictions ne seraient levées que lorsqu’il serait certain que personne, hormis les personnes mises en quarantaine, n’est infecté par le bytebacterium. En tant qu’expert en science des données le plus réputé du pays, vous êtes chargé d’analyser les données du système de surveillance et de déterminer quand les restrictions pourront effectivement être levées.

Byteland compte $n$ personnes et, au départ, chacune peut être saine ou infectée par le bytebacterium. Après la fermeture des frontières, $k$ événements se produisent successivement, parmi les types suivants :

• Le système de surveillance vous apprend qu’un groupe de personnes se rencontre. Si l’une d’elles est infectée, elles le deviennent toutes (et le restent indéfiniment). Un tel contact social est le seul moyen de contracter la maladie (contrairement aux premiers articles de presse, il est en réalité impossible de tomber malade en touchant des surfaces contaminées).

• Une personne donnée passe un test de dépistage du bytebacterium dont le résultat est négatif.

• Une personne donnée passe un test de dépistage du bytebacterium dont le résultat est positif. Elle est immédiatement mise en quarantaine et ne participe plus à aucun contact social (bien qu’il puisse arriver qu’elle passe encore un autre test par la suite [1]).

• Vous recevez une requête du ministre de la Santé pour déterminer si les restrictions peuvent déjà être supprimées, c’est-à-dire si toutes les informations acquises jusqu’ici permettent de prouver que personne, hormis les personnes en quarantaine, ne peut être infecté. Si quelqu’un peut encore être infecté, vous devez donner un exemple d’une telle personne, conformément aux directives du ministère (décrites dans la section Sortie).

Votre solution doit implémenter un algorithme en ligne : vous devez répondre à chaque requête immédiatement après l’avoir reçue, sans lire les parties suivantes de l’entrée.

[1] Vous vous demandez peut-être pourquoi faire passer un test de dépistage à une telle personne alors que son résultat sera forcément positif. L’auteur de ce problème a adressé une demande à ce sujet au ministère de la Santé de Byteland, mais a été informé que le délai légal de réponse était prolongé de trois mois en raison de la complexité du dossier.

Entrée

L’interprétation correcte des données d’entrée dépend de la valeur courante de la variable $\mathit{shift}$. Au début de chaque cas de test, cette variable est initialisée à $0$, puis ses valeurs dépendent des réponses fournies par votre programme. Ce format d’entrée vise à garantir que votre implémentation répond à chaque requête immédiatement après l’avoir lue.

La fonction de décodage est définie ainsi :

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

où $p$ est un entier vérifiant $1 \le p \le n$, et $\bmod$ désigne le reste de la division entière.

La première ligne de l’entrée contient le nombre de cas de test $z$ ($1 \le z \le 1\,000$). Les descriptions des cas de test suivent.

La première ligne contient deux entiers $n$ et $k$ ($1 \le n \le 500\,000$, $1 \le k \le 1\,000\,000$), indiquant respectivement le nombre de personnes et d’événements. Les personnes sont numérotées de $1$ à $n$.

Les $k$ lignes suivantes décrivent les événements successifs, chacun sous l’une des formes suivantes :

• La lettre K et un entier $c$ ($2 \le c \le n$), suivis de $c$ entiers distincts $p_1,\ldots,p_c$ ($1 \le p_i \le n$) : un contact social auquel participent les $c$ personnes d’identifiants $\operatorname{decode}(p_1),\ldots,\operatorname{decode}(p_c)$.

• La lettre N suivie d’un entier $p$ ($1 \le p \le n$) : la personne d’identifiant $\operatorname{decode}(p)$ passe un test de dépistage du bytebacterium dont le résultat est négatif.

• La lettre P suivie d’un entier $p$ ($1 \le p \le n$) : la personne d’identifiant $\operatorname{decode}(p)$ passe un test de dépistage du bytebacterium dont le résultat est positif. Elle est immédiatement mise en quarantaine et ne participe plus à aucun contact social (et tout test ultérieur qu’elle passe est nécessairement positif).

• La lettre Q suivie d’un entier $p$ ($1 \le p \le n$) : une requête du ministère dont la valeur de départ (voir la section Sortie) est $\operatorname{decode}(p)$.

Les sommes des valeurs de $n$ et de $k$ sur tous les cas de test ne dépassent pas respectivement $500\,000$ et $1\,000\,000$. La somme des valeurs de $c$ sur toutes les requêtes de tous les cas de test ne dépasse pas $1\,000\,000$.

Sortie

Pour chaque cas de test, affichez une ligne par requête (événement de type Q) de ce cas.

Si, au moment de la $i$-ième requête, on peut prouver que personne, hormis les personnes en quarantaine, ne peut être infecté, la $i$-ième ligne doit contenir le mot TAK [2]. Dans ce cas, la variable $\mathit{shift}$ prend la valeur $0$.

Sinon, la $i$-ième ligne doit contenir le mot NIE suivi d’un entier. Si $\operatorname{decode}(p)$ est la valeur de départ de la requête, cet entier doit être l’identifiant de la première personne de la suite $(\operatorname{decode}(p),\operatorname{decode}(p)+1,\ldots,n,1,2,\ldots,\operatorname{decode}(p)-1)$ qui pourrait être infectée par le bytebacterium mais n’est pas en quarantaine. Ce nombre devient la nouvelle valeur de $\mathit{shift}$.

[2] Il peut arriver qu’à un moment tous les habitants de Byteland soient en quarantaine. Dans ce cas, l’affirmation est évidemment vraie et votre programme doit afficher TAK.

Remarques

• La variable $\mathit{shift}$ ne change pas de valeur lors des événements de type K, N ou P.

• Les résultats positifs et négatifs des tests décrivent toujours un scénario cohérent. Autrement dit, pour chaque cas de test, il existe au moins un ensemble de personnes initialement infectées pour lequel la suite d’événements de l’entrée ne comporte aucune contradiction.

Exemples

Entrée 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

Sortie 1

NIE 5
NIE 1
TAK
TAK

• Après décodage, l’entrée ci-dessus se présente ainsi :

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

Remarque

• Avant la première requête, les personnes $3$, $4$ et $5$ se rencontrent, puis les personnes $5$ et $6$ se rencontrent, puis la personne $3$ obtient un résultat négatif. À la réception de la première requête, toutes les informations recueillies permettent les conclusions suivantes, en commençant à sa valeur de départ $3$. La personne $3$ est forcément saine (elle vient d’obtenir un résultat négatif). La personne $4$ est également forcément saine : elle ne pouvait pas être infectée lors de la première rencontre, sinon elle aurait infecté les personnes $3$ et $5$, ce qui contredirait le résultat négatif obtenu plus tard par la personne $3$ ; depuis, la personne $4$ n’a eu aucune possibilité de s’infecter, elle est donc encore saine. La personne $5$ pourrait être infectée : elle était forcément saine lors de sa rencontre avec $3$ et $4$, mais a ensuite rencontré la personne $6$, dont l’état de santé ne peut être déduit des informations disponibles. La réponse est donc NIE 5 et $\mathit{shift}$ prend la valeur $5$.

• Après la première requête, la personne $6$ obtient un résultat positif, puis les personnes $1$ et $5$ se rencontrent, puis la personne $5$ obtient un résultat positif. À la réception de la deuxième requête, toutes les informations recueillies permettent les conclusions suivantes, en commençant à sa valeur de départ $3$. Les personnes $3$ et $4$ sont forcément saines. Les personnes $5$ et $6$ sont en quarantaine. La personne $1$ pourrait être infectée (on peut même être certain qu’elle l’est, mais votre programme n’a pas besoin de distinguer ces deux cas). La réponse est donc NIE 1 et $\mathit{shift}$ prend la valeur $1$.

• Ensuite, la personne $1$ obtient un résultat positif, puis les personnes $2$ et $4$ se rencontrent, puis la personne $4$ obtient un résultat négatif. À la réception de la deuxième requête, on peut tirer les conclusions suivantes, en commençant à la valeur de départ $5$. Les personnes $5$, $6$ et $1$ sont en quarantaine. La personne $2$ est forcément saine en raison du résultat négatif obtenu par la personne $4$. Les personnes $3$ et $4$ sont également forcément saines. La réponse est donc TAK, car on peut prouver que toutes les personnes hors quarantaine ($2$, $3$ et $4$) sont forcément saines. La variable $\mathit{shift}$ prend la valeur $0$.

• Après la troisième requête, la personne $2$ obtient un résultat négatif. Comme on peut facilement le voir, cette partie de l’entrée est en fait sans importance : après la première réponse TAK, toutes les réponses doivent être TAK jusqu’à la fin de ce cas de test.