Dies ist ein interaktives Problem.

Das Spiel „Klempner Mariusz“ (Plumber Mariusz) besteht aus $n + 1$ Leveln (nummeriert von 0 bis $n$), von denen jedes $k$ Versionen hat (nummeriert von 0 bis $k - 1$). Jede Version jedes Levels (außer dem letzten) endet mit zwei Rohren — dem linken und dem rechten — und Mariusz muss in eines davon springen. Jedes Rohr enthält eine bestimmte Anzahl von Münzen und führt zu einer der Versionen des nächsten Levels. Genau zwei Rohre führen zu jeder Version jedes Levels (außer Level null); dies können beliebige zwei unter den $2 \cdot k$ Rohren sein, die aus allen $k$ Versionen des vorherigen Levels herausführen.

Ein einzelner Durchlauf besteht darin, eine Version von Level null zu wählen und anschließend $n$-mal das linke oder rechte Rohr zu wählen, und das Ergebnis des Durchlaufs ist die Gesamtzahl der in den $n$ besuchten Rohren gesammelten Münzen. Wir erfahren weder, wie viele Münzen sich in den einzelnen Rohren befanden, noch welche Versionen der Level besucht wurden. Die Münzen in den Rohren werden immer auf ihre Anfangswerte zurückgesetzt, sodass alle Durchläufe unabhängig sind. Ein Durchlauf kann daher durch die folgende Funktion dargestellt werden:

int rozgrywka(int ver, string s), wobei $\text{ver} \in [0, k - 1]$ ist und $s$ eine Zeichenkette aus $n$ Buchstaben L und P ist.

Beachten Sie, dass L und P den polnischen Wörtern für links bzw. rechts entsprechen.

Sie dürfen bis zu $300\,000$ Testdurchläufe durchführen und deren Ergebnisse erfahren. Danach erhalten Sie bis zu $10\,000$ Anfragen zu Durchläufen. Ihre Aufgabe ist es, deren Ergebnisse zu bestimmen.

Jeder Test steht vor Beginn der Interaktion fest (d. h. der Interaktor ist nicht adaptiv). Ein Test enthält einen gerichteten gewichteten Graphen mit $(n + 1) \cdot k$ Knoten, die in $n + 1$ Schichten (Leveln) angeordnet sind, sowie $q$ Anfragen $(\text{ver}, s)$. Jeder Knoten (außer denen in der letzten Schicht) hat zwei ausgehende Kanten (links und rechts), die jeweils durch eine Münzanzahl $c \in [1, 10^8]$ und eine Zielversion $v \in [0, k - 1]$ beschrieben werden. Beachten Sie, dass jeder Knoten außer denen in Schicht null den Eingangsgrad genau 2 hat.

Puffer leeren (Buffer flushing)

Nach der Ausgabe jeder Zeile müssen Sie den Ausgabepuffer leeren (flushen), damit der Interaktor die Ausgabezeile erhält. Beispielsweise können Sie in C++ eine Zeile mit einem Ausrufezeichen mittels cout << "!" << endl; oder printf("!\n"); fflush(stdout); ausgeben. In Python können Sie print("!", flush=True) verwenden. Wir garantieren kein stabiles Verhalten des Interaktors, wenn Sie mehrere Zeilen ausgeben, ohne nach jeder einzelnen zu flushen, oder wenn Sie viele Zeilen ausgeben, ohne die Antworten des Interaktors einzulesen. Ihr Programm darf keine Dateien öffnen.

Interaktionsprotokoll

Der vollständige Kommunikationsablauf ist unten beschrieben:

• Lesen Sie die erste Zeile mit zwei ganzen Zahlen $n$ und $k$ ($1 \le n, k \le 20$) ein — es gibt $n + 1$ Level mit jeweils $k$ Versionen.
• Führen Sie bis zu $300\,000$-mal einen Testdurchlauf durch:
  • Geben Sie eine Zeile der Form ? ver s (ohne Anführungszeichen) aus, wobei $\text{ver} \in [0, k - 1]$ ist und $s$ eine Zeichenkette aus $n$ Buchstaben L und P ist. Flush.
  • Lesen Sie die nächste Zeile mit dem Ergebnis des Durchlaufs ein — eine ganze Zahl $x$ ($n \le x \le n \cdot 10^8 \le 2 \cdot 10^9$).
• Geben Sie eine Zeile aus, die ein einzelnes Zeichen ! (Ausrufezeichen) enthält. Flush.
• Lesen Sie die nächste Zeile mit einer ganzen Zahl $q$ ($1 \le q \le 10\,000$) ein — die Anzahl der Anfragen.
• Für jede der $q$ Anfragen:
  • Lesen Sie die nächste Zeile mit einer ganzen Zahl $\text{ver}$ und einer Zeichenkette $s$ (gleiche Grenzen wie oben) ein.
  • Geben Sie eine Zeile mit dem Ergebnis des Durchlaufs (einer ganzen Zahl) aus. Flush.

Die Abbildung zeigt den ersten Beispieltest ($n = 2; k = 4$). Zwei abschließende Anfragen sind gestrichelt markiert: rozgrywka(0, "LL") $= 20 + 3 = 23$ und rozgrywka(1, "PL") $= 9 + 10 = 19$.

Beispiel

Hier ist ein beispielhafter Kommunikationsablauf:

Hinweis

Im Anhang (Sie können ihn im Reiter „attachment“ auf QOJ herunterladen) finden Sie (inkorrekte) Beispiellösungen G.cpp und G.py, die die Kommunikation korrekt durchführen, aber die Ergebnisse falsch berechnen. Das Verzeichnis enthält außerdem: einen Beispiel-Checker Gsoc.cpp und Beispieltests (G0a.in, G0b.in, G0c.in sowie einen großen Zufallstest G0d.in mit $n = k = 20$). Das Format der Testdateien ist im Kommentar am Anfang von Gsoc.cpp beschrieben.

Der Beispiel-Checker Gsoc.cpp unterscheidet sich von dem auf QOJ verwendeten Checker. Er überprüft möglicherweise nicht die Eingabe oder die Argumente der Durchlauffunktion.

Sie können Ihre Lösung mit dem Skript run.sh ausführen. Der Befehl nimmt das kompilierte Programm und den Namen der Testdatei entgegen. Um beispielsweise die Beispielprogramme auf dem Beispieltest G0a.in auszuführen:

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