Byteland hat gerade seine Grenzen geschlossen, weil in den Nachbarländern ein neuer Stamm von bytebacterium entdeckt wurde. Untersuchungen zeigen, dass dieser Stamm nicht nur hoch ansteckend ist, sondern auch keinerlei Reaktion des Immunsystems der Einwohner von Byteland auslöst. Wer einmal infiziert ist, bleibt daher lebenslang infiziert und steckt weiterhin andere an (oder zumindest so lange, bis ein wirksames Heilmittel entdeckt wird).

Um die Ausbreitung von bytebacterium einzudämmen, führte die Regierung von Byteland weitreichende Beschränkungen ein und startete das National Invigilation System, das die Überwachung aller sozialen Interaktionen im Land ermöglicht. Es wurde angekündigt, dass die Beschränkungen erst aufgehoben werden, wenn sicher ist, dass außer den unter Quarantäne gestellten Personen niemand mit bytebacterium infiziert ist. Als renommiertester Datenwissenschaftsexperte des Landes wurdest du damit beauftragt, die Daten des Überwachungssystems zu analysieren und festzustellen, wann die Beschränkungen tatsächlich aufgehoben werden können.

In Byteland leben $n$ Menschen. Zu Beginn kann jeder von ihnen entweder gesund oder mit bytebacterium infiziert sein. Nach der Grenzschließung finden nacheinander $k$ Ereignisse der folgenden Arten statt:

• Du erfährst vom Überwachungssystem, dass sich eine Gruppe von Menschen trifft. Ist einer von ihnen infiziert, werden alle ebenfalls infiziert (und bleiben es auf unbestimmte Zeit). Solche sozialen Kontakte sind die einzige Möglichkeit, sich anzustecken (entgegen ersten Presseberichten ist eine Erkrankung durch das Berühren infizierter Oberflächen tatsächlich unmöglich).

• Eine bestimmte Person macht einen Test auf bytebacterium, dessen Ergebnis negativ ist.

• Eine bestimmte Person macht einen Test auf bytebacterium, dessen Ergebnis positiv ist. Diese Person wird sofort unter Quarantäne gestellt und nimmt ab diesem Zeitpunkt an keinen sozialen Kontakten mehr teil (obwohl sie später möglicherweise erneut getestet wird [1]).

• Du erhältst vom Gesundheitsminister eine Anfrage, ob die Beschränkungen bereits aufgehoben werden können, also ob sich anhand aller bisher gesammelten Informationen beweisen lässt, dass außer den Personen unter Quarantäne niemand infiziert sein kann. Falls irgendeine Person noch infiziert sein könnte, musst du gemäß den Richtlinien des Ministeriums (im Abschnitt Ausgabe beschrieben) ein Beispiel für eine solche Person angeben.

Deine Lösung muss einen Onlinealgorithmus implementieren: Du musst jede Anfrage unmittelbar nach ihrem Empfang beantworten können, ohne spätere Teile der Eingabe zu lesen.

[1] Du fragst dich vielleicht, warum jemand eine solche Person auf bytebacterium testen sollte, wenn doch klar ist, dass das Ergebnis positiv sein muss. Der Autor dieser Aufgabe hat eine entsprechende Anfrage an das Gesundheitsministerium von Byteland gerichtet, wurde aber darüber informiert, dass die gesetzliche Antwortfrist wegen der Komplexität des vorliegenden Falls um drei Monate verlängert wurde.

Eingabe

Die korrekte Interpretation der Eingabedaten hängt vom aktuellen Wert der Variablen $\mathit{shift}$ ab. Zu Beginn jedes Testfalls wird $\mathit{shift}$ auf $0$ gesetzt; ihre späteren Werte hängen von den Antworten deines Programms ab. Dieses Eingabeformat soll sicherstellen, dass deine Implementierung jede Anfrage unmittelbar nach dem Einlesen beantwortet.

Die Dekodierungsfunktion ist wie folgt definiert:

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

Dabei ist $p$ eine ganze Zahl mit $1\le p\le n$, und $\bmod$ bezeichnet die Bildung des Rests bei ganzzahliger Division.

Die erste Eingabezeile enthält die Anzahl der Testfälle $z$ ($1\le z\le 1\,000$). Danach folgen die Beschreibungen der Testfälle.

Die erste Zeile enthält zwei ganze Zahlen $n$ und $k$ ($1\le n\le 500\,000$, $1\le k\le 1\,000\,000$), die die Anzahl der Menschen beziehungsweise der Ereignisse angeben. Die Menschen sind von $1$ bis $n$ nummeriert.

Die nächsten $k$ Zeilen beschreiben die aufeinanderfolgenden Ereignisse in jeweils einer der folgenden Formen:

• Der Buchstabe K und eine ganze Zahl $c$ ($2\le c\le n$), gefolgt von $c$ verschiedenen ganzen Zahlen $p_1,\ldots,p_c$ ($1\le p_i\le n$): ein sozialer Kontakt, an dem $c$ Menschen mit den Kennungen $\operatorname{decode}(p_1),\ldots,\operatorname{decode}(p_c)$ teilnehmen.

• Der Buchstabe N, gefolgt von einer ganzen Zahl $p$ ($1\le p\le n$): Die Person mit der Nummer $\operatorname{decode}(p)$ macht einen Test auf bytebacterium mit negativem Ergebnis.

• Der Buchstabe P, gefolgt von einer ganzen Zahl $p$ ($1\le p\le n$): Die Person mit der Nummer $\operatorname{decode}(p)$ macht einen Test auf bytebacterium mit positivem Ergebnis. Sie wird sofort unter Quarantäne gestellt und nimmt von diesem Zeitpunkt an an keinen sozialen Kontakten mehr teil (jeder weitere Test dieser Person wird zwangsläufig ebenfalls positiv ausfallen).

• Der Buchstabe Q, gefolgt von einer ganzen Zahl $p$ ($1\le p\le n$): eine Anfrage des Ministeriums mit dem Startwert (siehe Abschnitt Ausgabe) $\operatorname{decode}(p)$.

Die Summen der Werte von $n$ und $k$ über alle Testfälle sind höchstens $500\,000$ beziehungsweise $1\,000\,000$. Die Summe der Werte von $c$ über alle Anfragen aller Testfälle ist höchstens $1\,000\,000$.

Ausgabe

Gib für jeden Testfall für jede darin vorkommende Anfrage (Ereignis vom Typ Q) eine Zeile aus.

Falls zum Zeitpunkt der $i$-ten Anfrage bewiesen werden kann, dass außer den Personen unter Quarantäne niemand infiziert sein kann, soll die $i$-te Zeile das Wort TAK [2] enthalten. In diesem Fall wird der Wert von $\mathit{shift}$ auf $0$ gesetzt.

Andernfalls soll die $i$-te Zeile das Wort NIE enthalten, gefolgt von einer einzelnen ganzen Zahl. Ist $\operatorname{decode}(p)$ der Startwert der Anfrage, muss diese Zahl die Kennung der ersten Person in der Folge $(\operatorname{decode}(p),\operatorname{decode}(p)+1,\ldots,n,1,2,\ldots,\operatorname{decode}(p)-1)$ sein, die möglicherweise mit bytebacterium infiziert ist, aber nicht unter Quarantäne steht. Diese Zahl wird zum neuen Wert von $\mathit{shift}$.

[2] Es kann vorkommen, dass irgendwann alle Einwohner von Byteland unter Quarantäne stehen. In diesem Fall ist die Aussage selbstverständlich trivialerweise wahr und dein Programm soll „TAK“ ausgeben.

Hinweis

• Der Wert von $\mathit{shift}$ ändert sich bei Ereignissen vom Typ K, N oder P nicht.

• Die positiven und negativen Testergebnisse beschreiben immer ein mögliches Szenario. Das heißt, für jeden Testfall gibt es mindestens eine Menge anfangs infizierter Personen, für die die in der Eingabe beschriebene Ereignisfolge keine Widersprüche enthält.

Beispiele

Eingabe 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

Ausgabe 1

NIE 5
NIE 1
TAK
TAK

• Nach dem Dekodieren sieht die obige Eingabe wie folgt aus:

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

Hinweis

• Vor der ersten Anfrage treffen sich die Personen $3$, $4$ und $5$, danach die Personen $5$ und $6$, und anschließend erhält Person $3$ ein negatives Testergebnis. Bei der ersten Anfrage können wir anhand aller bisher gesammelten Informationen folgende Schlüsse ziehen (beginnend beim Startwert $3$ der Anfrage). Person $3$ muss gesund sein (sie hat gerade ein negatives Testergebnis erhalten). Person $4$ muss ebenfalls gesund sein (sie kann beim ersten Treffen nicht infiziert gewesen sein, denn sonst hätte sie die Personen $3$ und $5$ angesteckt, was dem späteren negativen Testergebnis von Person $3$ widersprechen würde; seitdem hatte Person $4$ keine Möglichkeit, sich anzustecken, und muss daher jetzt gesund sein). Person $5$ könnte infiziert sein (sie muss beim Treffen mit $3$ und $4$ gesund gewesen sein, traf sich später jedoch mit Person $6$, deren Gesundheitszustand sich aus den verfügbaren Informationen nicht ableiten lässt). Die Antwort lautet daher NIE 5, und $\mathit{shift}$ erhält den Wert $5$.

• Nach der ersten Anfrage erhält Person $6$ ein positives Testergebnis, danach treffen sich die Personen $1$ und $5$, und anschließend erhält Person $5$ ein positives Testergebnis. Bei der zweiten Anfrage können wir anhand aller bisher gesammelten Informationen folgende Schlüsse ziehen (beginnend beim Startwert $3$ der Anfrage). $3$ und $4$ müssen gesund sein. $5$ und $6$ stehen unter Quarantäne. Person $1$ könnte infiziert sein (tatsächlich können wir sogar sicher sein, dass sie infiziert sein muss, aber dein Programm muss diese beiden Fälle nicht unterscheiden). Die Antwort lautet daher NIE 1, und $\mathit{shift}$ erhält den Wert $1$.

• Danach erhält Person $1$ ein positives Testergebnis, anschließend treffen sich die Personen $2$ und $4$, und dann erhält Person $4$ ein negatives Testergebnis. Bei der zweiten Anfrage können wir folgende Schlüsse ziehen (beginnend beim Startwert $5$). Die Personen $5$, $6$ und $1$ stehen unter Quarantäne. Person $2$ muss aufgrund des negativen Testergebnisses von Person $4$ gesund sein. Auch die Personen $3$ und $4$ müssen gesund sein. Die Antwort lautet daher TAK, denn es lässt sich beweisen, dass alle Personen außerhalb der Quarantäne ($2$, $3$ und $4$) gesund sein müssen. Der Wert von $\mathit{shift}$ wird auf $0$ gesetzt.

• Nach der dritten Anfrage erhält Person $2$ ein negatives Testergebnis. Wie leicht zu erkennen ist, ist dieser Teil der Eingabe tatsächlich irrelevant: Nach der ersten Antwort TAK müssen bis zum Ende des jeweiligen Testfalls ausschließlich Antworten TAK folgen.