Ini adalah soal interaktif.

Permainan "Tukang Ledeng Mariusz" (Plumber Mariusz) terdiri dari $n + 1$ level (dinomori dari 0 hingga $n$), yang masing-masing memiliki $k$ versi (dinomori dari 0 hingga $k - 1$). Setiap versi dari setiap level (kecuali level terakhir) berakhir dengan dua pipa — kiri dan kanan — dan Mariusz harus melompat ke salah satunya. Setiap pipa berisi sejumlah koin dan mengarah ke salah satu versi dari level berikutnya. Tepat dua pipa mengarah ke setiap versi dari setiap level (kecuali level nol); kedua pipa ini bisa berupa dua pipa mana saja di antara $2 \cdot k$ pipa yang keluar dari semua $k$ versi pada level sebelumnya.

Satu kali permainan terdiri dari memilih sebuah versi dari level nol lalu memilih pipa kiri atau kanan sebanyak $n$ kali, dan hasil dari permainan tersebut adalah total banyaknya koin yang dikumpulkan di $n$ pipa yang dikunjungi. Kita tidak mengetahui berapa banyak koin di setiap pipa ataupun versi mana saja dari level-level tersebut yang dikunjungi. Koin-koin di dalam pipa selalu diatur ulang ke nilai awalnya, sehingga semua permainan bersifat independen. Oleh karena itu, sebuah permainan dapat direpresentasikan oleh fungsi:

int rozgrywka(int ver, string s), dengan $\text{ver} \in [0, k - 1]$ dan $s$ adalah sebuah string yang terdiri dari $n$ huruf L dan P.

Perhatikan bahwa L dan P masing-masing bersesuaian dengan kata bahasa Polandia untuk kiri dan kanan.

Anda dapat melakukan hingga $300\,000$ permainan uji coba dan mempelajari hasilnya. Setelah itu, Anda akan menerima hingga $10\,000$ kueri tentang permainan. Tugas Anda adalah menentukan hasil-hasilnya.

Setiap uji sudah ditetapkan sebelum interaksi dimulai (yaitu interaktor tidak adaptif). Sebuah uji berisi graf berarah berbobot dengan $(n + 1) \cdot k$ simpul yang disusun dalam $n + 1$ lapisan (level), serta $q$ kueri $(\text{ver}, s)$. Setiap simpul (kecuali yang berada di lapisan terakhir) memiliki dua sisi keluar (kiri dan kanan), masing-masing dijelaskan oleh jumlah koin $c \in [1, 10^8]$ dan versi tujuan $v \in [0, k - 1]$. Ingat bahwa setiap simpul kecuali yang berada di lapisan nol memiliki derajat masuk tepat 2.

Pengosongan buffer (Buffer flushing)

Setelah mengeluarkan setiap baris Anda harus melakukan flush pada buffer keluaran, agar interaktor menerima baris keluaran tersebut. Sebagai contoh, di C++ Anda dapat mengeluarkan baris berisi tanda seru menggunakan cout << "!" << endl; atau menggunakan printf("!\n"); fflush(stdout);. Di Python Anda dapat menggunakan print("!", flush=True). Kami tidak menjamin perilaku interaktor yang stabil jika Anda mengeluarkan beberapa baris tanpa melakukan flush setelah masing-masing baris, atau jika Anda mengeluarkan banyak baris tanpa membaca respons interaktor. Program Anda tidak boleh membuka berkas apa pun.

Protokol Interaksi

Alur komunikasi lengkapnya dijelaskan di bawah ini:

• Baca baris pertama yang berisi dua bilangan bulat $n$ dan $k$ ($1 \le n, k \le 20$) — terdapat $n + 1$ level, masing-masing dengan $k$ versi.
• Hingga $300\,000$ kali, lakukan permainan uji coba:
  • Keluarkan satu baris berbentuk ? ver s (tanpa tanda kutip), dengan $\text{ver} \in [0, k - 1]$ dan $s$ adalah string berisi $n$ huruf L dan P. Flush.
  • Baca baris berikutnya yang berisi hasil permainan — sebuah bilangan bulat $x$ ($n \le x \le n \cdot 10^8 \le 2 \cdot 10^9$).
• Keluarkan satu baris yang berisi satu karakter ! (tanda seru). Flush.
• Baca baris berikutnya yang berisi sebuah bilangan bulat $q$ ($1 \le q \le 10\,000$) — banyaknya kueri.
• Untuk masing-masing dari $q$ kueri:
  • Baca baris berikutnya yang berisi sebuah bilangan bulat $\text{ver}$ dan sebuah string $s$ (batas yang sama seperti di atas).
  • Keluarkan satu baris yang berisi hasil permainan (sebuah bilangan bulat). Flush.

Ilustrasi di atas menunjukkan uji sampel pertama ($n = 2; k = 4$). Dua kueri akhir ditandai menggunakan garis putus-putus: rozgrywka(0, "LL") $= 20 + 3 = 23$ dan rozgrywka(1, "PL") $= 9 + 10 = 19$.

Contoh

Berikut adalah contoh alur komunikasi:

Catatan

Pada lampiran (Anda dapat mengunduhnya di tab "attachment" di QOJ) Anda akan menemukan solusi sampel (yang salah) G.cpp dan G.py yang melakukan komunikasi dengan benar, tetapi menghitung hasil dengan salah. Direktori tersebut juga mencakup: pemeriksa sampel Gsoc.cpp dan uji sampel (G0a.in, G0b.in, G0c.in, serta uji acak besar G0d.in dengan $n = k = 20$). Format berkas uji dijelaskan dalam komentar di bagian awal Gsoc.cpp.

Pemeriksa sampel Gsoc.cpp berbeda dengan yang digunakan di QOJ. Pemeriksa tersebut mungkin tidak memvalidasi masukan atau argumen dari fungsi permainan.

Anda dapat menjalankan solusi Anda menggunakan skrip run.sh. Perintah ini menerima program yang telah dikompilasi dan nama berkas uji. Sebagai contoh, untuk menjalankan program sampel pada uji sampel G0a.in:

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