אתם צופים בקבוצת ילדים שנהנים ממשחק ידידותי של Quartets. בשלב מסוים התחלתם לחשוד שחלק מהילדים מרמים. נראה שלילדים עצמם זה כלל לא מפריע. להפך, זה גורם להם ליהנות עוד יותר, במיוחד כשמישהו נתפס מרמה. כמתכנתים, התחלתם מיד לחשוב על דרכים לזהות רמאות רק מצפייה במשחק.

Quartets הוא משחק קלפים לארבעה שחקנים המשתמש בחפיסה של $32$ קלפים המחולקת ל-$8$ קבוצות של $4$ קלפים כל אחת. הקלפים האמיתיים מכילים לעיתים קרובות תמונות לימודיות, שעוזרות ללמוד גם עצמים בודדים וגם את סיווגם. לדוגמה, הקלפים עשויים להציג בעלי חיים, והקבוצות עשויות להתאים לקבוצות שונות של בעלי חיים (יונקים, זוחלים וכדומה).

ארבעה קלפים מקבוצה אחת, מחפיסת Quartets גרמנית של Wilhelm Busch דרך Wikimedia Commons, נחלת הכלל.

בתחילת המשחק כל שחקן מקבל $8$ קלפים, ושחקן $1$ מתחיל בתורו. בכל תור, שחקן שואל שחקן אחר אם יש לו קלף מסוים. אם לנשאל יש הקלף, עליו לתת אותו למבקש, והמבקש ממשיך בתורו באמצעות בקשת קלף נוסף מכל אחד מהשחקנים. אם לנשאל אין הקלף, תורו של המבקש מסתיים והנשאל מתחיל בתורו. כלל חשוב קובע שלמבקש חייב להיות כבר לפחות קלף אחד מאותה קבוצה כמו הקלף שהוא מבקש.

אם במהלך תורו שחקן מחזיק קבוצה שלמה («רביעייה»), הוא רשאי להראותה לשחקנים האחרים, להניחה בצד ולקבל נקודה אחת. ארבעת קלפי הרביעייה יוצאים לצמיתות מהמשחק הנוכחי. אם בשלב כלשהו אין לשחקן עוד קלפים, הוא פורש מהמשחק. אם היה זה תורו, התור עובר לשחקן הבא לפי הסדר $1$-$2$-$3$-$4$-$1$-$\ldots$ שעדיין מחזיק קלפים. אם לאף שחקן אין קלפים, המשחק מסתיים והשחקן בעל מספר הנקודות הגבוה ביותר מוכרז כמנצח.

אסור לבקש קלפים שכבר הוצאו מהמשחק, ואסור לבקש קלף משחקן שפרש מהמשחק.

רמאות ב-Quartets אפשרית בשני מצבים שבהם שחקן טוען בשקר שיש לו (או שאין לו) קלף כלשהו. בפרט, מתרחשת רמאות אם

• שחקן מבקש קלף אף שאין לו שום קלף מהקבוצה המתאימה, או

• שחקן שנשאל טוען שאין לו הקלף המבוקש, אף שיש לו אותו.

מובן שרמאות מתגלה לעיתים קרובות רק בהמשך. תאורטית, יריב ערני יכול בסופו של דבר לגלות כל רמאות, כי כל הקלפים נחשפים בשלב כלשהו לפני סוף המשחק.

שימו לב שבקשת קלף שלא ייתכן שיהיה בידי הנשאל (למשל משום שהוא בידו של המבקש עצמו) אינה צעד נבון במיוחד, אך כשלעצמה אינה נחשבת רמאות.

קלט

השורה הראשונה מכילה מספר שלם $n$ ($1 \le n \le 1000$), מספר הפעולות הרצופות במשחק Quartets אחד מתחילתו. כל אחת מ-$n$ השורות הבאות מתארת פעולה אחת. כל פעולה מתוארת בשורה אחת ועשויה להיות אחת מהבאות:

• x A y sk yes — שחקן $x$ מבקש משחקן $y$ את הקלף $sk$, ושחקן $y$ מוסר אותו לשחקן $x$;

• x A y sk no — שחקן $x$ מבקש משחקן $y$ את הקלף $sk$, שחקן $y$ טוען שאין לו אותו ומתחיל בתורו;

• x Q s — שחקן $x$ מניח בצד את הרביעייה $s$.

בכל הפעולות, $x$ ו-$y$ ($1 \le x,y \le 4$, $x \ne y$) הם מספרים שלמים המציינים את השחקנים; $s$ ($1 \le s \le 8$) הוא מספר שלם בן ספרה אחת המציין קבוצה/רביעייה; ו-$k \in \{\mathrm{A},\mathrm{B},\mathrm{C},\mathrm{D}\}$ הוא תו המזהה את ארבעת הקלפים בקבוצה. לפיכך הקלפים $sk$ מסומנים 1A, 1B, 1C, 1D, 2A, 2B, …, 8C, 8D. ארבעת הקלפים שהספרה הראשונה שלהם זהה יוצרים קבוצה אחת.

הרצף הנתון מתאר משחק תקין בין ארבעה שחקנים. כלומר, למעט שתי דרכי הרמאות האפשריות שהוזכרו, כל הפעולות מקיימות את כל הכללים.

פלט

אם קיימת חלוקה התחלתית אפשרית של הקלפים שבה רצף הפעולות מתאים למשחק (אולי חלקי) שבו כל השחקנים מקיימים את הכללים, הדפיסו yes. אחרת הדפיסו no, ובשורה הבאה את מספר הפעולה הראשונה שאחריה ודאי ששחקן כלשהו רימה. הפעולות ממוספרות ברצף החל מ-$1$, וגם פעולות הנחת רביעיות בצד נספרות.

דוגמאות

קלט 1

4
1 A 2 3C no
2 A 3 3A yes
2 A 4 3D yes
2 A 1 3C no

פלט 1

no
4

הסבר

שחקנים $1$ ו-$2$ טוענים שניהם שאין להם 3C, ולאף אחד מהם לא היו 3A או 3D. לכן אחד מהם שיקר כשאמר שאין לו 3C, או ביקש 3C בלי להחזיק 3B (הקלף היחיד שנותר מקבוצה $3$).

קלט 2

6
1 A 2 3C no
2 A 3 3A yes
2 A 4 3D yes
2 A 1 3B no
1 A 4 5B yes
1 Q 5

פלט 2

yes