Byteland baru saja menutup perbatasannya karena galur baru bytebacterium ditemukan di negara-negara tetangga. Penelitian menunjukkan bahwa galur baru tersebut bukan hanya sangat menular, tetapi juga tidak memicu respons apa pun dari sistem kekebalan penduduk Byteland. Karena itu, siapa pun yang telah terinfeksi akan tetap terinfeksi dan terus menulari orang lain seumur hidup (atau setidaknya sampai pengobatan yang efektif ditemukan).

Untuk membatasi penyebaran bytebacterium, pemerintah Byteland memberlakukan pembatasan besar-besaran dan meluncurkan National Invigilation System, yang memungkinkan pemantauan semua interaksi sosial di negara tersebut. Diumumkan bahwa pembatasan hanya akan dicabut setelah dapat dipastikan bahwa tidak seorang pun, selain mereka yang telah dikarantina, terinfeksi bytebacterium. Sebagai pakar ilmu data paling terkenal di negara tersebut, Anda dipercayai untuk menganalisis data dari sistem pengawasan dan menentukan kapan pembatasan benar-benar dapat dicabut.

Ada $n$ orang di Byteland. Pada awalnya, setiap orang bisa saja sehat atau terinfeksi bytebacterium. Setelah perbatasan ditutup, $k$ peristiwa terjadi secara berurutan, dengan jenis-jenis berikut:

• Anda mengetahui dari sistem pengawasan bahwa sekelompok orang bertemu. Jika salah seorang di antaranya terinfeksi, semuanya juga menjadi terinfeksi (dan tetap demikian tanpa batas waktu). Kontak sosial seperti ini adalah satu-satunya cara untuk tertular penyakit tersebut (bertentangan dengan laporan pers awal, sakit akibat menyentuh permukaan terinfeksi sebenarnya tidak mungkin terjadi).

• Seseorang menjalani tes bytebacterium dan hasilnya negatif.

• Seseorang menjalani tes bytebacterium dan hasilnya positif. Orang tersebut langsung dikarantina dan sejak saat itu tidak akan mengikuti kontak sosial apa pun (meskipun mungkin saja ia masih menjalani tes lain di kemudian hari [1]).

• Anda menerima kueri dari menteri kesehatan untuk menentukan apakah pembatasan sudah dapat dihapus, yaitu apakah semua informasi yang diperoleh sejauh ini cukup untuk membuktikan bahwa tidak seorang pun, selain orang-orang yang dikarantina, mungkin terinfeksi. Jika masih ada orang yang mungkin terinfeksi, Anda harus memberikan contoh orang tersebut sesuai pedoman kementerian (dijelaskan di bagian Keluaran).

Solusi Anda harus mengimplementasikan algoritma daring, yaitu Anda harus dapat menjawab setiap kueri segera setelah menerimanya, tanpa membaca bagian masukan yang lebih lanjut.

[1] Anda mungkin bertanya-tanya mengapa seseorang melakukan tes bytebacterium terhadap orang seperti itu, padahal hasilnya jelas harus positif. Penulis soal ini telah mengirim pertanyaan terkait kepada Kementerian Kesehatan Byteland, tetapi diberi tahu bahwa batas waktu jawaban menurut undang-undang diperpanjang tiga bulan karena rumitnya kasus yang sedang ditangani.

Masukan

Penafsiran data masukan yang benar bergantung pada nilai variabel $\mathit{shift}$ saat ini. Pada awal setiap kasus uji, variabel $\mathit{shift}$ diinisialisasi menjadi $0$, sedangkan nilai-nilai selanjutnya bergantung pada jawaban yang diberikan program Anda. Format masukan ini dimaksudkan untuk memastikan bahwa implementasi Anda menjawab setiap kueri segera setelah membacanya.

Fungsi dekode didefinisikan sebagai berikut:

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

Di sini $p$ adalah bilangan bulat yang memenuhi $1\le p\le n$, sedangkan $\bmod$ adalah operasi mengambil sisa pembagian bilangan bulat.

Baris pertama masukan berisi banyaknya kasus uji $z$ ($1\le z\le 1\,000$). Deskripsi kasus-kasus uji menyusul.

Baris pertama berisi dua bilangan bulat $n$ dan $k$ ($1\le n\le 500\,000$, $1\le k\le 1\,000\,000$), masing-masing menyatakan banyaknya orang dan banyaknya peristiwa. Orang-orang diberi nomor dari $1$ hingga $n$.

$k$ baris berikutnya menjelaskan peristiwa-peristiwa secara berurutan, masing-masing dalam salah satu bentuk berikut:

• Huruf K dan sebuah bilangan bulat $c$ ($2\le c\le n$), diikuti $c$ bilangan bulat berbeda $p_1,\ldots,p_c$ ($1\le p_i\le n$): kontak sosial yang diikuti $c$ orang dengan pengenal $\operatorname{decode}(p_1),\ldots,\operatorname{decode}(p_c)$.

• Huruf N diikuti sebuah bilangan bulat $p$ ($1\le p\le n$): orang bernomor $\operatorname{decode}(p)$ menjalani tes bytebacterium yang memberikan hasil negatif.

• Huruf P diikuti sebuah bilangan bulat $p$ ($1\le p\le n$): orang bernomor $\operatorname{decode}(p)$ menjalani tes bytebacterium yang memberikan hasil positif. Orang tersebut langsung dikarantina dan sejak saat itu tidak mengikuti kontak sosial apa pun (dan setiap tes berikutnya terhadap orang tersebut pasti juga memberikan hasil positif).

• Huruf Q diikuti sebuah bilangan bulat $p$ ($1\le p\le n$): kueri kementerian dengan nilai awal (lihat bagian Keluaran) sama dengan $\operatorname{decode}(p)$.

Jumlah nilai $n$ dan $k$ untuk semua kasus uji masing-masing tidak melebihi $500\,000$ dan $1\,000\,000$. Jumlah nilai $c$ untuk semua kueri di semua kasus uji tidak melebihi $1\,000\,000$.

Keluaran

Untuk setiap kasus uji, keluarkan satu baris untuk setiap kueri (peristiwa jenis Q) yang muncul dalam kasus uji tersebut.

Jika pada saat kueri ke-$i$ dapat dibuktikan bahwa tidak mungkin ada orang yang terinfeksi (selain orang-orang yang dikarantina), baris ke-$i$ harus berisi kata TAK [2]. Dalam kasus ini, nilai variabel $\mathit{shift}$ berubah menjadi $0$.

Jika tidak, baris ke-$i$ harus berisi kata NIE diikuti sebuah bilangan bulat. Jika $\operatorname{decode}(p)$ adalah nilai awal kueri, bilangan tersebut harus merupakan pengenal orang pertama dalam urutan $(\operatorname{decode}(p),\operatorname{decode}(p)+1,\ldots,n,1,2,\ldots,\operatorname{decode}(p)-1)$ yang mungkin terinfeksi bytebacterium tetapi tidak dikarantina. Bilangan ini menjadi nilai baru variabel $\mathit{shift}$.

[2] Bisa saja pada suatu saat semua penduduk Byteland dikarantina. Tentu saja, dalam kasus tersebut pernyataan ini benar secara trivial dan program Anda harus mencetak “TAK”.

Catatan

• Variabel $\mathit{shift}$ tidak berubah nilainya pada peristiwa jenis K, N, atau P.

• Hasil tes positif dan negatif selalu menjelaskan skenario yang mungkin terjadi. Artinya, untuk setiap kasus uji ada setidaknya satu himpunan orang yang terinfeksi sejak awal sehingga urutan peristiwa dalam masukan tidak mengandung kontradiksi.

Contoh

Masukan 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

Keluaran 1

NIE 5
NIE 1
TAK
TAK

• Setelah didekode, masukan di atas menjadi seperti berikut:

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

Catatan

• Sebelum kueri pertama, orang $3$, $4$, dan $5$ bertemu, lalu orang $5$ dan $6$ bertemu, kemudian orang $3$ mendapatkan hasil tes negatif. Saat menerima kueri pertama, berdasarkan semua informasi yang terkumpul sejauh ini, kita dapat menarik kesimpulan berikut (mulai dari nilai awal kueri, yaitu $3$). Orang $3$ pasti sehat (ia baru saja mendapat hasil tes negatif). Orang $4$ juga pasti sehat (ia tidak mungkin telah terinfeksi saat pertemuan pertama, karena jika demikian ia akan menulari orang $3$ dan $5$, yang bertentangan dengan hasil tes negatif yang kemudian diperoleh orang $3$; sejak itu orang $4$ tidak memiliki kesempatan untuk terinfeksi, sehingga saat ini ia pasti sehat). Orang $5$ mungkin terinfeksi (ia pasti sehat saat bertemu $3$ dan $4$, tetapi kemudian bertemu orang $6$ yang status kesehatannya tidak dapat disimpulkan dari informasi yang tersedia). Jadi jawabannya adalah NIE 5 dan nilai $\mathit{shift}$ berubah menjadi $5$.

• Setelah kueri pertama, orang $6$ mendapatkan hasil tes positif, lalu orang $1$ dan $5$ bertemu, kemudian orang $5$ mendapatkan hasil tes positif. Saat menerima kueri kedua, berdasarkan semua informasi yang terkumpul sejauh ini, kita dapat menarik kesimpulan berikut (mulai dari nilai awal kueri, yaitu $3$). $3$ dan $4$ pasti sehat. $5$ dan $6$ dikarantina. Orang $1$ mungkin terinfeksi (sebenarnya kita bahkan dapat memastikan bahwa ia pasti terinfeksi, tetapi program Anda tidak perlu membedakan kedua keadaan tersebut). Jadi jawabannya adalah NIE 1 dan nilai $\mathit{shift}$ berubah menjadi $1$.

• Setelah itu, orang $1$ mendapatkan hasil tes positif, lalu orang $2$ dan $4$ bertemu, kemudian orang $4$ mendapatkan hasil tes negatif. Saat menerima kueri kedua, kita dapat menarik kesimpulan berikut (mulai dari nilai awal $5$). Orang $5$, $6$, dan $1$ dikarantina. Orang $2$ pasti sehat karena hasil tes negatif yang diperoleh orang $4$. Orang $3$ dan $4$ juga pasti sehat. Jadi jawabannya adalah TAK, karena dapat dibuktikan bahwa semua orang yang tidak dikarantina ($2$, $3$, dan $4$) pasti sehat. Nilai variabel $\mathit{shift}$ berubah menjadi $0$.

• Setelah kueri ketiga, orang $2$ mendapatkan hasil tes negatif. Seperti yang mudah Anda amati, bagian masukan ini sebenarnya tidak relevan: setelah jawaban TAK pertama, jawaban TAK harus terus muncul hingga akhir kasus uji tersebut.