أغلقت Byteland حدودها للتو بسبب اكتشاف سلالة جديدة من bytebacterium في البلدان المجاورة. أظهرت الأبحاث أن السلالة الجديدة ليست شديدة العدوى فحسب، بل إنها لا تثير أي استجابة من أجهزة المناعة لدى سكان Byteland، لذا يبقى كل من يصاب بالعدوى مصابًا، ويستمر في نقلها إلى الآخرين، طوال حياته (أو على الأقل حتى اكتشاف علاج فعال).

للحد من انتشار bytebacterium، فرضت حكومة Byteland قيودًا واسعة وأطلقت نظام المراقبة الوطني الذي يتيح مراقبة جميع التفاعلات الاجتماعية في البلاد. وأُعلن أن القيود لن تُرفع إلا عندما يصبح مؤكدًا أن لا أحد، باستثناء الأشخاص المعزولين، مصاب بعدوى bytebacterium. وبصفتك أشهر خبير في علم البيانات في البلاد، كُلّفت بتحليل بيانات نظام المراقبة وتحديد متى يمكن رفع القيود فعلًا.

يعيش في Byteland عدد من الأشخاص يساوي $n$، وفي البداية قد يكون كل منهم سليمًا أو مصابًا بعدوى bytebacterium. بعد إغلاق الحدود، تقع $k$ أحداث تباعًا من الأنواع التالية:

• تعلم من نظام المراقبة أن مجموعة من الأشخاص تلتقي. إذا كان أي منهم مصابًا، يصبحون جميعًا مصابين أيضًا ويظلون كذلك إلى أجل غير مسمى. هذا التواصل الاجتماعي هو الطريقة الوحيدة الممكنة للإصابة بالمرض (بخلاف التقارير الصحفية الأولية، يستحيل في الواقع الإصابة نتيجة لمس أسطح ملوثة).

• يخضع شخص معين لفحص bytebacterium وتكون النتيجة سلبية.

• يخضع شخص معين لفحص bytebacterium وتكون النتيجة إيجابية. يُعزل هذا الشخص فورًا ولا يشارك في أي تواصل اجتماعي بعد ذلك (مع احتمال إخضاعه لفحص آخر لاحقًا [1]).

• تتلقى استعلامًا من وزير الصحة لتحديد ما إذا كان يمكن إلغاء القيود الآن، أي ما إذا كانت جميع المعلومات المكتسبة حتى اللحظة تتيح إثبات أن لا أحد، باستثناء المعزولين، يمكن أن يكون مصابًا. إذا بقي أي شخص يُحتمل أن يكون مصابًا، فعليك إعطاء مثال على مثل هذا الشخص وفقًا لإرشادات الوزارة المبينة في قسم الإخراج.

يجب أن ينفذ حلك خوارزمية آنية: عليك أن تكون قادرًا على الإجابة عن كل استعلام فور تلقيه دون قراءة أي أجزاء لاحقة من الإدخال.

[1] قد تتساءل لماذا يُجرى فحص bytebacterium لمثل هذا الشخص، مع وضوح أن نتيجته ستكون إيجابية. أرسل مؤلف المسألة استفسارًا بهذا الشأن إلى وزارة الصحة في Byteland، لكنه أُبلغ بتمديد المهلة القانونية للرد ثلاثة أشهر نظرًا لتعقيد القضية.

الإدخال

يعتمد التفسير الصحيح لبيانات الإدخال على القيمة الحالية للمتغير $\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$ عبر جميع حالات الاختبار $500\,000$، ولا يتجاوز مجموع قيم $k$ القيمة $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 حتى نهاية حالة الاختبار.