Detta är ett interaktivt problem.

Spelet "Rörmokaren Mariusz" (Plumber Mariusz) består av $n + 1$ nivåer (numrerade från 0 till $n$), som var och en har $k$ versioner (numrerade från 0 till $k - 1$). Varje version av varje nivå (utom den sista) slutar med två rör — det vänstra och det högra — och Mariusz måste hoppa ner i ett av dem. Varje rör innehåller ett visst antal mynt och leder till en av versionerna av nästa nivå. Exakt två rör leder till varje version av varje nivå (utom nivå noll); dessa kan vara vilka två som helst bland de $2 \cdot k$ rör som kommer ut från alla $k$ versioner av föregående nivå.

En enskild genomspelning består av att välja en version av nivå noll och sedan välja vänster eller höger rör $n$ gånger, och resultatet av genomspelningen är det totala antalet mynt som samlats in i de $n$ besökta rören. Vi får inte veta hur många mynt som fanns i varje rör eller vilka versioner av nivåerna som besöktes. Mynten i rören återställs alltid till sina ursprungliga värden, så alla genomspelningar är oberoende. En genomspelning kan därför representeras av funktionen:

int rozgrywka(int ver, string s), där $\text{ver} \in [0, k - 1]$ och $s$ är en sträng med $n$ bokstäver L och P.

Observera att L och P motsvarar de polska orden för vänster respektive höger.

Du får utföra upp till $300\,000$ testgenomspelningar och få reda på deras resultat. Därefter kommer du att få upp till $10\,000$ frågor om genomspelningar. Din uppgift är att bestämma deras resultat.

Varje test är fastställt innan interaktionen börjar (dvs. interaktorn är inte adaptiv). Ett test innehåller en riktad viktad graf med $(n + 1) \cdot k$ hörn ordnade i $n + 1$ lager (nivåer), samt $q$ frågor $(\text{ver}, s)$. Varje hörn (utom de i det sista lagret) har två utgående kanter (vänster och höger), var och en beskriven av ett myntantal $c \in [1, 10^8]$ och en version $v \in [0, k - 1]$ som den leder till. Kom ihåg att varje hörn utom de i lager noll har ingrad exakt 2.

Tömning av bufferten (Buffer flushing)

Efter att du har skrivit ut varje rad måste du tömma utdatabufferten (flush), så att interaktorn tar emot den utskrivna raden. Till exempel kan du i C++ skriva ut en rad som innehåller ett utropstecken med cout << "!" << endl; eller med printf("!\n"); fflush(stdout);. I Python kan du använda print("!", flush=True). Vi garanterar inte ett stabilt beteende hos interaktorn om du skriver ut flera rader utan att tömma bufferten efter var och en av dem, eller om du skriver ut många rader utan att läsa interaktorns svar. Ditt program får inte öppna några filer.

Interaktionsprotokoll

Hela kommunikationsflödet beskrivs nedan:

• Läs den första raden som innehåller två heltal $n$ och $k$ ($1 \le n, k \le 20$) — det finns $n + 1$ nivåer, var och en med $k$ versioner.
• Upp till $300\,000$ gånger, utför en testgenomspelning:
  • Skriv ut en rad på formen ? ver s (utan citattecken), där $\text{ver} \in [0, k - 1]$ och $s$ är en sträng med $n$ bokstäver L och P. Flush.
  • Läs nästa rad som innehåller resultatet av genomspelningen — ett heltal $x$ ($n \le x \le n \cdot 10^8 \le 2 \cdot 10^9$).
• Skriv ut en rad som innehåller ett enda tecken ! (utropstecken). Flush.
• Läs nästa rad som innehåller ett heltal $q$ ($1 \le q \le 10\,000$) — antalet frågor.
• För var och en av de $q$ frågorna:
  • Läs nästa rad som innehåller ett heltal $\text{ver}$ och en sträng $s$ (samma gränser som ovan).
  • Skriv ut en rad som innehåller resultatet av genomspelningen (ett heltal). Flush.

Illustrationen visar det första exempeltestet ($n = 2; k = 4$). Två slutliga frågor är markerade med streckade linjer: rozgrywka(0, "LL") $= 20 + 3 = 23$ och rozgrywka(1, "PL") $= 9 + 10 = 19$.

Exempel

Här är ett exempel på kommunikationsflöde:

Anmärkning

I bilagan (du kan ladda ner den under fliken "attachment" på QOJ) hittar du (felaktiga) exempellösningar G.cpp och G.py som utför kommunikationen korrekt, men beräknar resultaten felaktigt. Katalogen innehåller även: en exempelgranskare Gsoc.cpp och exempeltester (G0a.in, G0b.in, G0c.in, samt ett stort slumpmässigt test G0d.in med $n = k = 20$). Formatet på testfilerna beskrivs i kommentaren i början av Gsoc.cpp.

Exempelgranskaren Gsoc.cpp skiljer sig från den som används på QOJ. Den validerar eventuellt inte indata eller argumenten till genomspelningsfunktionen.

Du kan köra din lösning med skriptet run.sh. Kommandot tar det kompilerade programmet och namnet på testfilen. Till exempel, för att köra exempelprogrammen på exempeltestet G0a.in:

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