Byteland เพิ่งปิดพรมแดน เนื่องจากตรวจพบ bytebacterium สายพันธุ์ใหม่ในประเทศเพื่อนบ้าน งานวิจัยแสดงว่าสายพันธุ์ใหม่นี้ไม่เพียงแพร่เชื้อได้ง่ายมาก แต่ยังไม่กระตุ้นการตอบสนองใด ๆ ของระบบภูมิคุ้มกันของชาว Byteland ด้วย ดังนั้นเมื่อใครติดเชื้อแล้วก็จะติดเชื้อและแพร่เชื้อให้ผู้อื่นต่อไปตลอดชีวิต (หรืออย่างน้อยก็จนกว่าจะค้นพบวิธีรักษาที่ได้ผล)

เพื่อควบคุมการแพร่กระจายของ bytebacterium รัฐบาล Byteland จึงใช้มาตรการจำกัดอย่างกว้างขวางและเปิดใช้ National Invigilation System ซึ่งทำให้ติดตามปฏิสัมพันธ์ทางสังคมทั้งหมดในประเทศได้ มีการประกาศว่าจะยกเลิกมาตรการจำกัดก็ต่อเมื่อแน่ใจได้ว่าไม่มีใครติดเชื้อ bytebacterium ยกเว้นผู้ที่ถูกกักตัว ในฐานะผู้เชี่ยวชาญด้านวิทยาการข้อมูลที่มีชื่อเสียงที่สุดของประเทศ คุณได้รับมอบหมายให้วิเคราะห์ข้อมูลจากระบบเฝ้าระวังและพิจารณาว่าจะยกเลิกมาตรการจำกัดได้เมื่อใด

Byteland มีประชากร $n$ คน และในตอนเริ่มต้นแต่ละคนอาจมีสุขภาพดีหรือติดเชื้อ bytebacterium ก็ได้ หลังจากปิดพรมแดน จะมีเหตุการณ์ $k$ เหตุการณ์เกิดขึ้นตามลำดับ โดยมีประเภทดังต่อไปนี้:

• คุณทราบจากระบบเฝ้าระวังว่ามีคนกลุ่มหนึ่งมาพบกัน หากมีใครในกลุ่มติดเชื้อ ทุกคนจะติดเชื้อด้วย (และจะติดเชื้อต่อไปอย่างไม่มีกำหนด) การติดต่อทางสังคมเช่นนี้เป็นหนทางเดียวที่จะติดโรคได้ (ตรงกันข้ามกับรายงานข่าวในช่วงแรก การป่วยเพราะสัมผัสพื้นผิวที่มีเชื้อนั้นเป็นไปไม่ได้จริง ๆ)

• บุคคลคนหนึ่งเข้ารับการตรวจ bytebacterium และผลเป็นลบ

• บุคคลคนหนึ่งเข้ารับการตรวจ bytebacterium และผลเป็นบวก บุคคลนั้นจะถูกกักตัวทันที และจะไม่เข้าร่วมการติดต่อทางสังคมใด ๆ อีกนับจากนั้น (แม้ว่าภายหลังอาจมีการตรวจบุคคลนั้นอีกครั้ง [1])

• คุณได้รับคำถามจากรัฐมนตรีว่าการกระทรวงสาธารณสุขให้พิจารณาว่าสามารถยกเลิกมาตรการจำกัดได้แล้วหรือไม่ กล่าวคือ ข้อมูลทั้งหมดที่ได้รับจนถึงขณะนั้นทำให้พิสูจน์ได้หรือไม่ว่าไม่มีใครที่อาจติดเชื้อ ยกเว้นผู้ที่ถูกกักตัว หากยังมีบุคคลใดที่อาจติดเชื้อ คุณต้องยกตัวอย่างบุคคลดังกล่าวตามแนวทางของกระทรวง (อธิบายในส่วนข้อมูลส่งออก)

คำตอบของคุณต้องใช้อัลกอริทึมแบบออนไลน์ กล่าวคือ คุณต้องตอบแต่ละคำถามได้ทันทีที่ได้รับ โดยไม่อ่านส่วนของข้อมูลนำเข้าที่อยู่ถัดไป

[1] คุณอาจสงสัยว่าทำไมใครจึงตรวจ bytebacterium ให้บุคคลเช่นนั้น ทั้งที่ชัดเจนว่าผลต้องเป็นบวก ผู้เขียนโจทย์นี้ได้ส่งข้อสอบถามที่เกี่ยวข้องไปยังกระทรวงสาธารณสุขของ Byteland แต่ได้รับแจ้งว่าระยะเวลาตอบกลับตามกฎหมายถูกขยายออกไปสามเดือน เนื่องจากกรณีดังกล่าวมีความซับซ้อน

ข้อมูลนำเข้า

การตีความข้อมูลนำเข้าอย่างถูกต้องจะขึ้นอยู่กับค่าปัจจุบันของตัวแปร $\mathit{shift}$ เมื่อเริ่มแต่ละกรณีทดสอบ ตัวแปร $\mathit{shift}$ จะถูกกำหนดค่าเริ่มต้นเป็น $0$ ส่วนค่าในภายหลังจะขึ้นอยู่กับคำตอบที่โปรแกรมของคุณให้ รูปแบบข้อมูลนำเข้านี้มีจุดประสงค์เพื่อให้แน่ใจว่าการเขียนโปรแกรมของคุณตอบแต่ละคำถามทันทีหลังจากอ่านคำถามนั้น

ฟังก์ชันถอดรหัสนิยามดังนี้:

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

โดย $p$ เป็นจำนวนเต็มที่เป็นไปตาม $1\le p\le n$ และ $\bmod$ คือการดำเนินการหาเศษจากการหารจำนวนเต็ม

บรรทัดแรกของข้อมูลนำเข้ามีจำนวนกรณีทดสอบ $z$ ($1\le z\le 1\,000$) จากนั้นเป็นรายละเอียดของแต่ละกรณีทดสอบ

บรรทัดแรกมีจำนวนเต็มสองจำนวน $n$ และ $k$ ($1\le n\le 500\,000$, $1\le k\le 1\,000\,000$) ซึ่งระบุจำนวนคนและจำนวนเหตุการณ์ตามลำดับ ผู้คนมีหมายเลขตั้งแต่ $1$ ถึง $n$

$k$ บรรทัดถัดไปอธิบายเหตุการณ์ตามลำดับ โดยแต่ละเหตุการณ์มีรูปแบบใดรูปแบบหนึ่งดังต่อไปนี้:

• ตัวอักษร K และจำนวนเต็ม $c$ ($2\le c\le n$) ตามด้วยจำนวนเต็มที่แตกต่างกัน $c$ จำนวน $p_1,\ldots,p_c$ ($1\le p_i\le n$): การติดต่อทางสังคมที่มีคน $c$ คนซึ่งมีหมายเลข $\operatorname{decode}(p_1),\ldots,\operatorname{decode}(p_c)$ เข้าร่วม

• ตัวอักษร N ตามด้วยจำนวนเต็ม $p$ ($1\le p\le n$): บุคคลหมายเลข $\operatorname{decode}(p)$ เข้ารับการตรวจ bytebacterium และได้ผลลบ

• ตัวอักษร P ตามด้วยจำนวนเต็ม $p$ ($1\le p\le n$): บุคคลหมายเลข $\operatorname{decode}(p)$ เข้ารับการตรวจ bytebacterium และได้ผลบวก บุคคลนี้จะถูกกักตัวทันที และจะไม่เข้าร่วมการติดต่อทางสังคมใด ๆ อีกนับจากนั้น (ทั้งนี้ การตรวจบุคคลนี้ครั้งต่อไปทุกครั้งย่อมให้ผลบวกเช่นกัน)

• ตัวอักษร Q ตามด้วยจำนวนเต็ม $p$ ($1\le p\le n$): คำถามของกระทรวงที่มีค่าเริ่มต้น (ดูส่วนข้อมูลส่งออก) เท่ากับ $\operatorname{decode}(p)$

ผลรวมของค่า $n$ และ $k$ ในทุกกรณีทดสอบไม่เกิน $500\,000$ และ $1\,000\,000$ ตามลำดับ ผลรวมของค่า $c$ ในทุกคำถามของทุกกรณีทดสอบไม่เกิน $1\,000\,000$

ข้อมูลส่งออก

สำหรับแต่ละกรณีทดสอบ ให้แสดงหนึ่งบรรทัดต่อแต่ละคำถาม (เหตุการณ์ประเภท Q) ที่ปรากฏในกรณีทดสอบนั้น

หาก ณ เวลาที่ได้รับคำถามที่ $i$ สามารถพิสูจน์ได้ว่าไม่มีใครติดเชื้อได้เลย (ยกเว้นบุคคลที่ถูกกักตัว) บรรทัดที่ $i$ ต้องมีคำว่า TAK [2] ในกรณีนี้ ตัวแปร $\mathit{shift}$ จะเปลี่ยนค่าเป็น $0$

มิฉะนั้น บรรทัดที่ $i$ ต้องมีคำว่า NIE ตามด้วยจำนวนเต็มหนึ่งจำนวน หาก $\operatorname{decode}(p)$ คือค่าเริ่มต้นของคำถาม จำนวนเต็มนั้นต้องเป็นหมายเลขของบุคคลคนแรกในลำดับ $(\operatorname{decode}(p),\operatorname{decode}(p)+1,\ldots,n,1,2,\ldots,\operatorname{decode}(p)-1)$ ที่อาจติดเชื้อ bytebacterium แต่ไม่ได้ถูกกักตัว จำนวนนี้จะกลายเป็นค่าใหม่ของตัวแปร $\mathit{shift}$

[2] อาจเกิดกรณีที่ชาว Byteland ทุกคนถูกกักตัว ณ เวลาหนึ่ง แน่นอนว่าในกรณีนี้ข้อความดังกล่าวเป็นจริงโดยปริยาย และโปรแกรมของคุณต้องแสดง “TAK”

หมายเหตุ

• ตัวแปร $\mathit{shift}$ จะไม่เปลี่ยนค่าเมื่อเกิดเหตุการณ์ประเภท K, N หรือ P

• ผลตรวจที่เป็นบวกและลบจะอธิบายสถานการณ์ที่เป็นไปได้เสมอ กล่าวคือ สำหรับแต่ละกรณีทดสอบ จะมีเซตของผู้ติดเชื้อตั้งแต่เริ่มต้นอย่างน้อยหนึ่งเซตที่ทำให้ลำดับเหตุการณ์ในข้อมูลนำเข้าไม่มีข้อขัดแย้งใด ๆ

ตัวอย่าง

ข้อมูลนำเข้า 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

ข้อมูลส่งออก 1

NIE 5
NIE 1
TAK
TAK

• หลังจากถอดรหัสแล้ว ข้อมูลนำเข้าข้างต้นจะมีลักษณะดังต่อไปนี้:

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

หมายเหตุ

• ก่อนคำถามแรก บุคคล $3$, $4$ และ $5$ พบกัน จากนั้นบุคคล $5$ และ $6$ พบกัน แล้วบุคคล $3$ ได้ผลตรวจลบ เมื่อได้รับคำถามแรก เราสามารถใช้ข้อมูลทั้งหมดที่รวบรวมมาจนถึงตอนนั้นเพื่อสรุปได้ดังนี้ (เริ่มจากค่าเริ่มต้นของคำถามคือ $3$) บุคคล $3$ ต้องมีสุขภาพดี (เขาเพิ่งได้ผลตรวจลบ) บุคคล $4$ ก็ต้องมีสุขภาพดีเช่นกัน (เธอไม่อาจติดเชื้อในเวลาที่พบกันครั้งแรก เพราะไม่เช่นนั้นเธอจะทำให้บุคคล $3$ และ $5$ ติดเชื้อ ซึ่งขัดแย้งกับผลตรวจลบที่บุคคล $3$ ได้รับในภายหลัง ตั้งแต่นั้นบุคคล $4$ ไม่มีโอกาสติดเชื้อ ดังนั้นขณะนี้เธอต้องมีสุขภาพดี) บุคคล $5$ อาจติดเชื้อ (เขาต้องมีสุขภาพดีตอนพบกับ $3$ และ $4$ แต่ภายหลังเขาพบกับบุคคล $6$ ซึ่งเราไม่อาจสรุปสถานะสุขภาพได้จากข้อมูลที่มี) ดังนั้นคำตอบคือ NIE 5 และ $\mathit{shift}$ เปลี่ยนค่าเป็น $5$

• หลังคำถามแรก บุคคล $6$ ได้ผลตรวจบวก จากนั้นบุคคล $1$ และ $5$ พบกัน แล้วบุคคล $5$ ได้ผลตรวจบวก เมื่อได้รับคำถามที่สอง เราสามารถใช้ข้อมูลทั้งหมดที่รวบรวมมาจนถึงตอนนั้นเพื่อสรุปได้ดังนี้ (เริ่มจากค่าเริ่มต้นของคำถามคือ $3$) $3$ และ $4$ ต้องมีสุขภาพดี $5$ และ $6$ ถูกกักตัว บุคคล $1$ อาจติดเชื้อ (อันที่จริง เราถึงกับมั่นใจได้ว่าเธอต้องติดเชื้อ แต่โปรแกรมของคุณไม่จำเป็นต้องแยกแยะสองกรณีนี้) ดังนั้นคำตอบคือ NIE 1 และ $\mathit{shift}$ เปลี่ยนค่าเป็น $1$

• หลังจากนั้น บุคคล $1$ ได้ผลตรวจบวก จากนั้นบุคคล $2$ และ $4$ พบกัน แล้วบุคคล $4$ ได้ผลตรวจลบ เมื่อได้รับคำถามที่สอง เราสามารถสรุปได้ดังนี้ (เริ่มจากค่าเริ่มต้น $5$) บุคคล $5$, $6$ และ $1$ ถูกกักตัว บุคคล $2$ ต้องมีสุขภาพดีเนื่องจากผลตรวจลบที่บุคคล $4$ ได้รับ บุคคล $3$ และ $4$ ก็ต้องมีสุขภาพดีเช่นกัน ดังนั้นคำตอบคือ TAK เพราะสามารถพิสูจน์ได้ว่าทุกคนที่ไม่ได้ถูกกักตัว ($2$, $3$ และ $4$) ต้องมีสุขภาพดี ตัวแปร $\mathit{shift}$ เปลี่ยนค่าเป็น $0$

• หลังคำถามที่สาม บุคคล $2$ ได้ผลตรวจลบ คุณจะสังเกตได้ง่ายว่าส่วนนี้ของข้อมูลนำเข้าไม่มีผลแต่อย่างใด: หลังคำตอบ TAK ครั้งแรก คำตอบจะต้องเป็น TAK ต่อไปจนจบกรณีทดสอบนั้น