โจทย์ข้อนี้เป็นโจทย์แบบโต้ตอบ (Interactive Problem)

เกม "ช่างประปา Mariusz" (Plumber Mariusz) ประกอบด้วยด่านทั้งหมด $n + 1$ ด่าน (มีหมายเลขตั้งแต่ 0 ถึง $n$) ซึ่งแต่ละด่านมี $k$ เวอร์ชัน (มีหมายเลขตั้งแต่ 0 ถึง $k - 1$) แต่ละเวอร์ชันของทุกด่าน (ยกเว้นด่านสุดท้าย) จะสิ้นสุดลงด้วยท่อสองท่อ — ท่อซ้ายและท่อขวา — และ Mariusz ต้องกระโดดลงไปในท่อใดท่อหนึ่ง แต่ละท่อจะมีเหรียญอยู่จำนวนหนึ่งและนำไปสู่หนึ่งในเวอร์ชันของด่านถัดไป จะมีท่อสองท่อพอดีที่นำไปสู่แต่ละเวอร์ชันของแต่ละด่าน (ยกเว้นด่านศูนย์) ซึ่งอาจเป็นท่อสองท่อใดก็ได้ในบรรดาท่อ $2 \cdot k$ ท่อที่ออกมาจากทั้ง $k$ เวอร์ชันของด่านก่อนหน้า

การเล่นหนึ่งรอบประกอบด้วยการเลือกเวอร์ชันของด่านศูนย์ แล้วเลือกท่อซ้ายหรือท่อขวาเป็นจำนวน $n$ ครั้ง และผลลัพธ์ของการเล่นรอบนั้นคือจำนวนเหรียญรวมที่เก็บได้ในท่อทั้ง $n$ ท่อที่ผ่าน เราจะไม่ทราบว่าในแต่ละท่อมีเหรียญอยู่กี่เหรียญ หรือได้ผ่านเวอร์ชันใดของด่านต่างๆ บ้าง เหรียญในท่อจะถูกรีเซ็ตกลับเป็นค่าเริ่มต้นเสมอ ดังนั้นการเล่นทุกรอบจึงเป็นอิสระต่อกัน การเล่นหนึ่งรอบจึงสามารถแทนได้ด้วยฟังก์ชัน:

int rozgrywka(int ver, string s) โดยที่ $\text{ver} \in [0, k - 1]$ และ $s$ คือสตริงของตัวอักษร L และ P ความยาว $n$ ตัว

สังเกตว่า 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$ คือสตริงของตัวอักษร L และ P จำนวน $n$ ตัว แล้วล้างบัฟเฟอร์
  • อ่านบรรทัดถัดไปซึ่งประกอบด้วยผลลัพธ์ของการเล่น — จำนวนเต็ม $x$ ($n \le x \le n \cdot 10^8 \le 2 \cdot 10^9$)
• แสดงผลบรรทัดที่มีอักขระตัวเดียวคือ ! (เครื่องหมายอัศเจรีย์) แล้วล้างบัฟเฟอร์
• อ่านบรรทัดถัดไปซึ่งประกอบด้วยจำนวนเต็ม $q$ ($1 \le q \le 10\,000$) — จำนวนคำถาม
• สำหรับแต่ละคำถามใน $q$ คำถาม:
  • อ่านบรรทัดถัดไปซึ่งประกอบด้วยจำนวนเต็ม $\text{ver}$ และสตริง $s$ (ขอบเขตเหมือนด้านบน)
  • แสดงผลบรรทัดซึ่งประกอบด้วยผลลัพธ์ของการเล่น (จำนวนเต็ม) แล้วล้างบัฟเฟอร์

ภาพประกอบแสดงชุดทดสอบตัวอย่างแรก ($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