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$ ושל $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$ בהמשך; מאז לא הייתה לה אפשרות להידבק, ולכן היא בריאה כעת. האדם $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 עד סוף מקרה הבדיקה.