Este es un problema interactivo.

El juego «Fontanero Mariusz» (Plumber Mariusz) consta de $n + 1$ niveles (numerados de 0 a $n$), cada uno de los cuales tiene $k$ versiones (numeradas de 0 a $k - 1$). Cada versión de cada nivel (excepto el último) termina con dos tuberías — la izquierda y la derecha — y Mariusz debe saltar dentro de una de ellas. Cada tubería contiene cierta cantidad de monedas y conduce a una de las versiones del siguiente nivel. Exactamente dos tuberías conducen a cada versión de cada nivel (excepto el nivel cero); estas pueden ser cualesquiera dos entre las $2 \cdot k$ tuberías que salen de todas las $k$ versiones del nivel anterior.

Una partida consiste en elegir una versión del nivel cero y luego elegir la tubería izquierda o derecha $n$ veces, y el resultado de la partida es el número total de monedas recolectadas en las $n$ tuberías visitadas. No sabemos cuántas monedas había en cada tubería ni qué versiones de los niveles fueron visitadas. Las monedas en las tuberías siempre se restablecen a sus valores iniciales, por lo que todas las partidas son independientes. Por lo tanto, una partida puede representarse mediante la función:

int rozgrywka(int ver, string s), donde $\text{ver} \in [0, k - 1]$ y $s$ es una cadena de $n$ letras L y P.

Observa que L y P corresponden a las palabras en polaco para izquierda y derecha, respectivamente.

Puedes realizar hasta $300\,000$ partidas de prueba y conocer sus resultados. Después de eso, recibirás hasta $10\,000$ consultas sobre partidas. Tu tarea es determinar sus resultados.

Cada prueba está fijada antes de que comience la interacción (es decir, el interactor no es adaptativo). Una prueba contiene un grafo dirigido con pesos con $(n + 1) \cdot k$ vértices dispuestos en $n + 1$ capas (niveles), y $q$ consultas $(\text{ver}, s)$. Cada vértice (excepto los de la última capa) tiene dos aristas salientes (izquierda y derecha), cada una descrita por una cantidad de monedas $c \in [1, 10^8]$ y una versión $v \in [0, k - 1]$ a la que conduce. Recuerda que todo vértice, excepto los de la capa cero, tiene grado de entrada exactamente 2.

Vaciado del búfer (Buffer flushing)

Después de imprimir cada línea debes vaciar el búfer de salida (flush), para que el interactor reciba la línea impresa. Por ejemplo, en C++ puedes imprimir una línea que contenga un signo de exclamación usando cout << "!" << endl; o usando printf("!\n"); fflush(stdout);. En Python puedes usar print("!", flush=True). No garantizamos un comportamiento estable del interactor si imprimes múltiples líneas sin vaciar el búfer después de cada una de ellas, o si imprimes muchas líneas sin leer las respuestas del interactor. Tu programa no puede abrir ningún archivo.

Protocolo de interacción

El flujo completo de comunicación se describe a continuación:

• Lee la primera línea que contiene dos enteros $n$ y $k$ ($1 \le n, k \le 20$) — hay $n + 1$ niveles, cada uno con $k$ versiones.
• Hasta $300\,000$ veces, realiza una partida de prueba:
  • Imprime una línea de la forma ? ver s (sin comillas), donde $\text{ver} \in [0, k - 1]$ y $s$ es una cadena de $n$ letras L y P. Flush.
  • Lee la siguiente línea que contiene el resultado de la partida — un entero $x$ ($n \le x \le n \cdot 10^8 \le 2 \cdot 10^9$).
• Imprime una línea que contenga un único carácter ! (signo de exclamación). Flush.
• Lee la siguiente línea que contiene un entero $q$ ($1 \le q \le 10\,000$) — el número de consultas.
• Para cada una de las $q$ consultas:
  • Lee la siguiente línea que contiene un entero $\text{ver}$ y una cadena $s$ (con los mismos límites que arriba).
  • Imprime una línea que contenga el resultado de la partida (un entero). Flush.

La ilustración muestra la primera prueba de ejemplo ($n = 2; k = 4$). Dos consultas finales están marcadas con líneas discontinuas: rozgrywka(0, "LL") $= 20 + 3 = 23$ y rozgrywka(1, "PL") $= 9 + 10 = 19$.

Ejemplo

Aquí tienes un ejemplo de flujo de comunicación:

Nota

En el archivo adjunto (puedes descargarlo en la pestaña «attachment» en QOJ) encontrarás soluciones de ejemplo (incorrectas) G.cpp y G.py que realizan la comunicación correctamente, pero calculan los resultados de forma incorrecta. El directorio también incluye: un verificador de ejemplo Gsoc.cpp y pruebas de ejemplo (G0a.in, G0b.in, G0c.in, y una prueba aleatoria grande G0d.in con $n = k = 20$). El formato de los archivos de prueba se describe en el comentario al principio de Gsoc.cpp.

El verificador de ejemplo Gsoc.cpp difiere del utilizado en QOJ. Es posible que no valide la entrada o los argumentos de la función de partida.

Puedes ejecutar tu solución usando el script run.sh. El comando recibe el programa compilado y el nombre del archivo de prueba. Por ejemplo, para ejecutar los programas de ejemplo en la prueba de ejemplo G0a.in:

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