Byteland właśnie zamknął swoje granice z powodu wykrycia nowego szczepu bytebacterium w sąsiednich krajach. Badania pokazują, że nowy szczep nie tylko jest wysoce zaraźliwy, lecz także nie wywołuje żadnej reakcji układu odpornościowego mieszkańców Bytelandu, więc osoba raz zakażona pozostanie taka — i będzie nadal zakażać innych — do końca życia (a przynajmniej do czasu odkrycia skutecznego lekarstwa).
Aby ograniczyć rozprzestrzenianie się bytebacterium, rząd Bytelandu wprowadził daleko idące ograniczenia i uruchomił Narodowy System Inwigilacji, pozwalający monitorować wszystkie kontakty społeczne w kraju. Ogłoszono, że ograniczenia zostaną zniesione dopiero wtedy, gdy będzie pewne, że nikt poza osobami objętymi kwarantanną nie jest zakażony bytebacterium. Jako najsłynniejszemu w kraju ekspertowi w dziedzinie analizy danych powierzono ci analizowanie danych z systemu inwigilacji i ustalenie, kiedy rzeczywiście można znieść ograniczenia.
W Bytelandzie mieszka $n$ osób i początkowo każda z nich może być zdrowa albo zakażona bytebacterium. Po zamknięciu granic następuje kolejno $k$ zdarzeń następujących typów:
Z systemu inwigilacji dowiadujesz się, że pewna grupa osób się spotyka. Jeśli choć jedna z nich jest zakażona, wszystkie również zostają zakażone (i pozostaną takie bezterminowo). Taki kontakt społeczny jest jedynym możliwym sposobem zakażenia się chorobą (wbrew początkowym doniesieniom prasowym zachorowanie wskutek dotknięcia zakażonych powierzchni jest w rzeczywistości niemożliwe).
Pewna osoba wykonuje test na bytebacterium i otrzymuje wynik ujemny.
Pewna osoba wykonuje test na bytebacterium i otrzymuje wynik dodatni. Osoba ta natychmiast zostaje objęta kwarantanną i od tej chwili nie uczestniczy w żadnych kontaktach społecznych (chociaż może się zdarzyć, że później zostanie jej wykonany kolejny test [1]).
Otrzymujesz zapytanie od ministra zdrowia, czy można już znieść ograniczenia, czyli czy wszystkie dotychczas uzyskane informacje pozwalają udowodnić, że nikt poza osobami objętymi kwarantanną nie może być zakażony. Jeśli ktokolwiek nadal może być zakażony, musisz podać przykład takiej osoby zgodnie z wytycznymi ministerstwa (opisanymi w sekcji Wyjście).
Twoje rozwiązanie musi realizować algorytm online — to znaczy musisz umieć odpowiedzieć na każde zapytanie natychmiast po jego otrzymaniu, bez czytania dalszych części wejścia.
[1] Możesz się zastanawiać, dlaczego ktokolwiek wykonywałby test na bytebacterium takiej osobie, skoro jest jasne, że wynik musi być dodatni. Autor zadania skierował stosowne zapytanie do Ministerstwa Zdrowia Bytelandu, ale został poinformowany, że ustawowy termin odpowiedzi został przedłużony o trzy miesiące ze względu na złożony charakter sprawy.
Wejście
Poprawna interpretacja danych wejściowych zależy od bieżącej wartości zmiennej $\mathit{shift}$. Na początku każdego przypadku testowego zmienna $\mathit{shift}$ jest inicjalizowana wartością $0$, a jej późniejsze wartości zależą od odpowiedzi zwracanych przez twój program. Taki format wejścia ma zapewnić, że twoja implementacja odpowiada na każde zapytanie natychmiast po jego odczytaniu.
Funkcja dekodująca jest zdefiniowana następująco:
$$ \operatorname{decode}(p)=((p-1+\mathit{shift})\bmod n)+1. $$
Tutaj $p$ jest liczbą całkowitą spełniającą $1 \le p \le n$, a $\bmod$ oznacza operację obliczania reszty z dzielenia całkowitego.
Pierwszy wiersz wejścia zawiera liczbę przypadków testowych $z$ ($1 \le z \le 1\,000$). Dalej następują opisy przypadków testowych.
Pierwszy wiersz zawiera dwie liczby całkowite $n$ i $k$ ($1 \le n \le 500\,000$, $1 \le k \le 1\,000\,000$), oznaczające odpowiednio liczbę osób i liczbę zdarzeń. Osoby są ponumerowane od $1$ do $n$.
Kolejne $k$ wierszy opisuje kolejne zdarzenia, z których każde ma jedną z następujących postaci:
Litera
Ki liczba całkowita $c$ ($2 \le c \le n$), po których następuje $c$ różnych liczb całkowitych $p_1,\ldots,p_c$ ($1 \le p_i \le n$) — kontakt społeczny, w którym uczestniczy $c$ osób o identyfikatorach $\operatorname{decode}(p_1),\ldots,\operatorname{decode}(p_c)$.Litera
N, po której następuje liczba całkowita $p$ ($1 \le p \le n$) — osoba o numerze $\operatorname{decode}(p)$ wykonuje test na bytebacterium, który daje wynik ujemny.Litera
P, po której następuje liczba całkowita $p$ ($1 \le p \le n$) — osoba o numerze $\operatorname{decode}(p)$ wykonuje test na bytebacterium, który daje wynik dodatni. Osoba ta natychmiast zostaje objęta kwarantanną i od tej chwili nie uczestniczy w żadnych kontaktach społecznych (a każdy kolejny wykonany jej test nieuchronnie również da wynik dodatni).Litera
Q, po której następuje liczba całkowita $p$ ($1 \le p \le n$) — zapytanie ministerstwa z wartością początkową (patrz sekcja Wyjście) równą $\operatorname{decode}(p)$.
Sumy wartości $n$ i $k$ po wszystkich przypadkach testowych nie przekraczają odpowiednio $500\,000$ i $1\,000\,000$. Suma wartości $c$ po wszystkich zapytaniach we wszystkich przypadkach testowych nie przekracza $1\,000\,000$.
Wyjście
Dla każdego przypadku testowego wypisz po jednym wierszu dla każdego występującego w nim zapytania (zdarzenia typu Q).
Jeśli w chwili $i$-tego zapytania można udowodnić, że nikt (poza osobami objętymi kwarantanną) nie może być zakażony, $i$-ty wiersz powinien zawierać słowo TAK [2]. W takim przypadku zmienna $\mathit{shift}$ zmienia wartość na $0$.
W przeciwnym razie $i$-ty wiersz powinien zawierać słowo NIE, a po nim jedną liczbę całkowitą. Jeśli $\operatorname{decode}(p)$ jest wartością początkową zapytania, liczba ta powinna być identyfikatorem pierwszej osoby w ciągu $(\operatorname{decode}(p),\operatorname{decode}(p)+1,\ldots,n,1,2,\ldots,\operatorname{decode}(p)-1)$, która może być zakażona bytebacterium, ale nie jest objęta kwarantanną. Liczba ta staje się nową wartością zmiennej $\mathit{shift}$.
[2] Może się zdarzyć, że w pewnej chwili wszyscy mieszkańcy Bytelandu będą objęci kwarantanną. Oczywiście wtedy to stwierdzenie jest trywialnie prawdziwe, a twój program powinien wypisać TAK.
Uwagi
Zmienna $\mathit{shift}$ nie zmienia wartości przy zdarzeniach typu
K,NaniP.Dodatnie i ujemne wyniki testów zawsze opisują możliwy scenariusz. To znaczy, że dla każdego przypadku testowego istnieje co najmniej jeden zbiór osób początkowo zakażonych, dla którego opisany na wejściu ciąg zdarzeń nie zawiera żadnych sprzeczności.
Przykład
Wejście 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
Wyjście 1
NIE 5 NIE 1 TAK TAK
- Po zdekodowaniu powyższe wejście wygląda następująco:
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
Uwagi
Przed pierwszym zapytaniem spotykają się osoby 3, 4 i 5, następnie osoby 5 i 6, po czym osoba 3 otrzymuje ujemny wynik testu. Po otrzymaniu pierwszego zapytania możemy, korzystając ze wszystkich dotychczas zgromadzonych informacji, wyciągnąć następujące wnioski (zaczynając od wartości początkowej zapytania 3). Osoba 3 musi być zdrowa (właśnie otrzymała ujemny wynik testu). Osoba 4 również musi być zdrowa (nie mogła być zakażona w chwili pierwszego spotkania, bo w przeciwnym razie zakaziłaby osoby 3 i 5, co byłoby sprzeczne z późniejszym ujemnym wynikiem testu osoby 3; od tamtej pory osoba 4 nie miała możliwości zakażenia się, więc obecnie musi być zdrowa). Osoba 5 może być zakażona (musiała być zdrowa podczas spotkania z osobami 3 i 4, ale później spotkała się z osobą 6, której stanu zdrowia nie da się ustalić z dostępnych informacji). Odpowiedź to zatem
NIE 5, a $\mathit{shift}$ zmienia wartość na $5$.Po pierwszym zapytaniu osoba 6 otrzymuje dodatni wynik testu, następnie spotykają się osoby 1 i 5, po czym osoba 5 otrzymuje dodatni wynik testu. Po otrzymaniu drugiego zapytania możemy, korzystając ze wszystkich dotychczas zgromadzonych informacji, wyciągnąć następujące wnioski (zaczynając od wartości początkowej zapytania 3). Osoby 3 i 4 muszą być zdrowe. Osoby 5 i 6 są objęte kwarantanną. Osoba 1 może być zakażona (w rzeczywistości możemy nawet mieć pewność, że musi być zakażona, ale twój program nie musi rozróżniać tych dwóch sytuacji). Odpowiedź to zatem
NIE 1, a $\mathit{shift}$ zmienia wartość na $1$.Następnie osoba 1 otrzymuje dodatni wynik testu, potem spotykają się osoby 2 i 4, po czym osoba 4 otrzymuje ujemny wynik testu. Po otrzymaniu drugiego zapytania możemy wyciągnąć następujące wnioski (zaczynając od wartości początkowej 5). Osoby 5, 6 i 1 są objęte kwarantanną. Osoba 2 musi być zdrowa ze względu na ujemny wynik testu osoby 4. Osoby 3 i 4 również muszą być zdrowe. Odpowiedź to zatem
TAK, ponieważ można udowodnić, że wszystkie osoby nieobjęte kwarantanną (2, 3 i 4) muszą być zdrowe. Zmienna $\mathit{shift}$ zmienia wartość na $0$.Po trzecim zapytaniu osoba 2 otrzymuje ujemny wynik testu. Jak łatwo zauważyć, ta część wejścia jest de facto nieistotna: po pierwszej odpowiedzi
TAKodpowiedziTAKmuszą pojawiać się aż do końca danego przypadku testowego.