Ceci est un problème interactif.

Le jeu « Mariusz le plombier » (Plumber Mariusz) se compose de $n + 1$ niveaux (numérotés de 0 à $n$), chacun ayant $k$ versions (numérotées de 0 à $k - 1$). Chaque version de chaque niveau (sauf le dernier) se termine par deux tuyaux — le gauche et le droit — et Mariusz doit sauter dans l'un d'eux. Chaque tuyau contient un certain nombre de pièces et mène à l'une des versions du niveau suivant. Exactement deux tuyaux mènent à chaque version de chaque niveau (sauf le niveau zéro) ; il peut s'agir de deux tuyaux quelconques parmi les $2 \cdot k$ tuyaux sortant de toutes les $k$ versions du niveau précédent.

Une partie consiste à choisir une version du niveau zéro, puis à choisir le tuyau gauche ou droit $n$ fois, et le résultat de la partie est le nombre total de pièces collectées dans les $n$ tuyaux visités. Nous n'apprenons pas combien de pièces se trouvaient dans chaque tuyau ni quelles versions des niveaux ont été visitées. Les pièces dans les tuyaux reviennent toujours à leurs valeurs initiales, de sorte que toutes les parties sont indépendantes. Une partie peut donc être représentée par la fonction :

int rozgrywka(int ver, string s), où $\text{ver} \in [0, k - 1]$ et $s$ est une chaîne de $n$ lettres L et P.

Notez que L et P correspondent respectivement aux mots polonais pour gauche et droite.

Vous pouvez effectuer jusqu'à $300\,000$ parties de test et apprendre leurs résultats. Après cela, vous recevrez jusqu'à $10\,000$ requêtes concernant des parties. Votre tâche consiste à déterminer leurs résultats.

Chaque test est fixé avant le début de l'interaction (c'est-à-dire que l'interacteur n'est pas adaptatif). Un test contient un graphe orienté pondéré avec $(n + 1) \cdot k$ sommets disposés en $n + 1$ couches (niveaux), et $q$ requêtes $(\text{ver}, s)$. Chaque sommet (sauf ceux de la dernière couche) a deux arêtes sortantes (gauche et droite), chacune décrite par un nombre de pièces $c \in [1, 10^8]$ et une version $v \in [0, k - 1]$ vers laquelle elle mène. Rappelez-vous que chaque sommet, sauf ceux de la couche zéro, a un degré entrant exactement égal à 2.

Vidage du tampon (Buffer flushing)

Après avoir affiché chaque ligne, vous devez vider le tampon de sortie (flush), afin que l'interacteur reçoive la ligne affichée. Par exemple, en C++, vous pouvez afficher une ligne contenant un point d'exclamation en utilisant cout << "!" << endl; ou en utilisant printf("!\n"); fflush(stdout);. En Python, vous pouvez utiliser print("!", flush=True). Nous ne garantissons pas un comportement stable de l'interacteur si vous affichez plusieurs lignes sans vider le tampon après chacune d'elles, ou si vous affichez de nombreuses lignes sans lire les réponses de l'interacteur. Votre programme ne doit ouvrir aucun fichier.

Protocole d'interaction

Le flux complet de communication est décrit ci-dessous :

• Lire la première ligne contenant deux entiers $n$ et $k$ ($1 \le n, k \le 20$) — il y a $n + 1$ niveaux, chacun avec $k$ versions.
• Jusqu'à $300\,000$ fois, effectuer une partie de test :
  • Afficher une ligne de la forme ? ver s (sans guillemets), où $\text{ver} \in [0, k - 1]$ et $s$ est une chaîne de $n$ lettres L et P. Flush.
  • Lire la ligne suivante contenant le résultat de la partie — un entier $x$ ($n \le x \le n \cdot 10^8 \le 2 \cdot 10^9$).
• Afficher une ligne contenant un seul caractère ! (point d'exclamation). Flush.
• Lire la ligne suivante contenant un entier $q$ ($1 \le q \le 10\,000$) — le nombre de requêtes.
• Pour chacune des $q$ requêtes :
  • Lire la ligne suivante contenant un entier $\text{ver}$ et une chaîne $s$ (mêmes limites que ci-dessus).
  • Afficher une ligne contenant le résultat de la partie (un entier). Flush.

L'illustration montre le premier test d'exemple ($n = 2; k = 4$). Deux requêtes finales sont marquées en pointillés : rozgrywka(0, "LL") $= 20 + 3 = 23$ et rozgrywka(1, "PL") $= 9 + 10 = 19$.

Exemple

Voici un exemple de flux de communication :

Note

Dans la pièce jointe (que vous pouvez télécharger dans l'onglet « attachment » sur QOJ), vous trouverez des solutions d'exemple (incorrectes) G.cpp et G.py qui effectuent la communication correctement, mais calculent les résultats de manière incorrecte. Le répertoire comprend également : un vérificateur d'exemple Gsoc.cpp et des tests d'exemple (G0a.in, G0b.in, G0c.in, ainsi qu'un grand test aléatoire G0d.in avec $n = k = 20$). Le format des fichiers de test est décrit dans le commentaire au début de Gsoc.cpp.

Le vérificateur d'exemple Gsoc.cpp diffère de celui utilisé sur QOJ. Il se peut qu'il ne valide pas l'entrée ou les arguments de la fonction de partie.

Vous pouvez exécuter votre solution à l'aide du script run.sh. La commande prend le programme compilé et le nom du fichier de test. Par exemple, pour exécuter les programmes d'exemple sur le test d'exemple G0a.in :

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