זוהי בעיה אינטראקטיבית.

המשחק "השרברב מריוש" (Plumber Mariusz) מורכב מ-$n + 1$ שלבים (הממוספרים מ-0 עד $n$), שלכל אחד מהם יש $k$ גרסאות (הממוספרות מ-0 עד $k - 1$). כל גרסה של כל שלב (למעט האחרון) מסתיימת בשני צינורות — השמאלי והימני — ומריוש חייב לקפוץ לאחד מהם. כל צינור מכיל מספר כלשהו של מטבעות ומוביל לאחת הגרסאות של השלב הבא. בדיוק שני צינורות מובילים לכל גרסה של כל שלב (למעט שלב אפס); אלו יכולים להיות כל שניים מבין $2 \cdot k$ הצינורות היוצאים מכל $k$ הגרסאות של השלב הקודם.

משחק בודד מורכב מבחירת גרסה של שלב אפס ולאחר מכן בחירת צינור שמאלי או ימני $n$ פעמים, והתוצאה של המשחק היא המספר הכולל של המטבעות שנאספו ב-$n$ הצינורות שבהם ביקרנו. איננו יודעים כמה מטבעות היו בכל צינור או באילו גרסאות של השלבים ביקרנו. המטבעות בצינורות תמיד מתאפסים לערכיהם ההתחלתיים, כך שכל המשחקים בלתי תלויים זה בזה. לפיכך, ניתן לייצג משחק באמצעות הפונקציה:

int rozgrywka(int ver, string s), כאשר $\text{ver} \in [0, k - 1]$ ו-$s$ היא מחרוזת בת $n$ אותיות L ו-P.

שימו לב כי L ו-P מתאימות למילים בפולנית עבור שמאל וימין בהתאמה.

באפשרותכם לבצע עד $300\,000$ משחקי ניסיון ולגלות את תוצאותיהם. לאחר מכן, תקבלו עד $10\,000$ שאילתות לגבי משחקים. המשימה שלכם היא לקבוע את תוצאותיהם.

כל מבחן קבוע מראש לפני תחילת האינטראקציה (כלומר, האינטראקטור אינו אדפטיבי). מבחן מכיל גרף מכוון ממושקל עם $(n + 1) \cdot k$ קודקודים המסודרים ב-$n + 1$ שכבות (שלבים), ו-$q$ שאילתות $(\text{ver}, s)$. לכל קודקוד (למעט אלו שבשכבה האחרונה) יש שתי קשתות יוצאות (שמאל וימין), שכל אחת מהן מתוארת על ידי מספר מטבעות $c \in [1, 10^8]$ וגרסה $v \in [0, k - 1]$ שאליה היא מובילה. זכרו שלכל קודקוד למעט אלו שבשכבה אפס יש דרגת כניסה השווה בדיוק ל-2.

ריקון החוצץ (Buffer flushing)

לאחר הדפסת כל שורה עליכם לרוקן את חוצץ הפלט (flush), כדי שהאינטראקטור יקבל את שורת הפלט. לדוגמה, ב-C++ תוכלו להדפיס שורה המכילה סימן קריאה באמצעות cout << "!" << endl; או באמצעות printf("!\n"); fflush(stdout);. ב-Python תוכלו להשתמש ב-print("!", flush=True). איננו מבטיחים התנהגות יציבה של האינטראקטור אם תדפיסו מספר שורות ללא ריקון החוצץ אחרי כל אחת מהן, או אם תדפיסו שורות רבות מבלי לקרוא את תגובות האינטראקטור. לתוכנית שלכם אסור לפתוח קבצים כלשהם.

פרוטוקול אינטראקציה

זרימת התקשורת המלאה מתוארת להלן:

• קראו את השורה הראשונה המכילה שני מספרים שלמים $n$ ו-$k$ ($1 \le n, k \le 20$) — ישנם $n + 1$ שלבים, לכל אחד $k$ גרסאות.
• עד $300\,000$ פעמים, בצעו משחק ניסיון:
  • הדפיסו שורה מהצורה ? ver s (ללא מירכאות), כאשר $\text{ver} \in [0, k - 1]$ ו-$s$ היא מחרוזת בת $n$ אותיות L ו-P. בצעו flush.
  • קראו את השורה הבאה המכילה את תוצאת המשחק — מספר שלם $x$ ($n \le x \le n \cdot 10^8 \le 2 \cdot 10^9$).
• הדפיסו שורה המכילה תו בודד ! (סימן קריאה). בצעו flush.
• קראו את השורה הבאה המכילה מספר שלם $q$ ($1 \le q \le 10\,000$) — מספר השאילתות.
• עבור כל אחת מ-$q$ השאילתות:
  • קראו את השורה הבאה המכילה מספר שלם $\text{ver}$ ומחרוזת $s$ (אותן מגבלות כמו לעיל).
  • הדפיסו שורה המכילה את תוצאת המשחק (מספר שלם). בצעו flush.

האיור מציג את מבחן הדוגמה הראשון ($n = 2; k = 4$). שתי שאילתות סופיות מסומנות בקווים מקווקווים: rozgrywka(0, "LL") $= 20 + 3 = 23$ ו-rozgrywka(1, "PL") $= 9 + 10 = 19$.

דוגמה

להלן דוגמה לזרימת תקשורת:

הערה

בקובץ המצורף (ניתן להוריד אותו בלשונית "attachment" ב-QOJ) תמצאו פתרונות לדוגמה (שגויים) G.cpp ו-G.py המבצעים את התקשורת בצורה תקינה, אך מחשבים את התוצאות באופן שגוי. התיקייה כוללת גם: בודק לדוגמה Gsoc.cpp ומבחנים לדוגמה (G0a.in, G0b.in, G0c.in, ומבחן אקראי גדול G0d.in עם $n = k = 20$). הפורמט של קובצי המבחן מתואר בהערה שבתחילת Gsoc.cpp.

הבודק לדוגמה Gsoc.cpp שונה מזה המשמש ב-QOJ. ייתכן שהוא אינו מאמת את הקלט או את הארגומנטים של פונקציית המשחק.

תוכלו להריץ את הפתרון שלכם באמצעות הסקריפט run.sh. הפקודה מקבלת את התוכנית המקומפלת ואת שם קובץ המבחן. לדוגמה, כדי להריץ את תוכניות הדוגמה על מבחן הדוגמה G0a.in:

• C++: g++ G.cpp -o G.e && ./run.sh "./G.e" G0a.in
• Python: ./run.sh "python3 G.py" G0a.in