Це інтерактивна задача.

Гра «Водопровідник Маріуш» (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. Скиньте буфер.
  • Зчитайте наступний рядок, що містить результат проходження — ціле число $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