Это интерактивная задача.

Игра «Водопроводчик Мариуш» (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