هذه مسألة تفاعلية.

تتكون لعبة «السباك ماريوش» (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