Dette er en interaktiv oppgave.

Spillet «Rørlegger Mariusz» (Plumber Mariusz) består av $n + 1$ nivåer (nummerert fra 0 til $n$), som hvert har $k$ versjoner (nummerert fra 0 til $k - 1$). Hver versjon av hvert nivå (unntatt det siste) ender med to rør — det venstre og det høyre — og Mariusz må hoppe inn i ett av dem. Hvert rør inneholder et visst antall mynter og fører til en av versjonene på neste nivå. Nøyaktig to rør fører til hver versjon av hvert nivå (unntatt nivå null); disse kan være hvilke som helst to blant de $2 \cdot k$ rørene som kommer ut fra alle de $k$ versjonene på forrige nivå.

En enkelt gjennomspilling består i å velge en versjon av nivå null og deretter velge venstre eller høyre rør $n$ ganger, og resultatet av gjennomspillingen er det totale antallet mynter samlet i de $n$ besøkte rørene. Vi får ikke vite hvor mange mynter som var i hvert rør eller hvilke versjoner av nivåene som ble besøkt. Myntene i rørene tilbakestilles alltid til startverdiene sine, så alle gjennomspillinger er uavhengige. En gjennomspilling kan derfor representeres ved funksjonen:

int rozgrywka(int ver, string s), der $\text{ver} \in [0, k - 1]$ og $s$ er en streng med $n$ bokstaver L og P.

Merk at L og P tilsvarer de polske ordene for henholdsvis venstre og høyre.

Du kan utføre opptil $300\,000$ testgjennomspillinger og få vite resultatene deres. Etter det vil du motta opptil $10\,000$ spørringer om gjennomspillinger. Oppgaven din er å bestemme resultatene deres.

Hver test er fastsatt før interaksjonen starter (dvs. interaktoren er ikke adaptiv). En test inneholder en rettet vektet graf med $(n + 1) \cdot k$ noder ordnet i $n + 1$ lag (nivåer), og $q$ spørringer $(\text{ver}, s)$. Hver node (unntatt de i det siste laget) har to utgående kanter (venstre og høyre), hver beskrevet av et myntantall $c \in [1, 10^8]$ og en versjon $v \in [0, k - 1]$ den fører til. Husk at hver node unntatt de i lag null har inngrad nøyaktig 2.

Tømming av bufferen (Buffer flushing)

Etter å ha skrevet ut hver linje må du tømme utdatabufferen (flush), slik at interaktoren mottar utskrevet linje. For eksempel kan du i C++ skrive ut en linje som inneholder et utropstegn ved å bruke cout << "!" << endl; eller ved å bruke printf("!\n"); fflush(stdout);. I Python kan du bruke print("!", flush=True). Vi garanterer ikke stabil oppførsel fra interaktoren hvis du skriver ut flere linjer uten å tømme bufferen etter hver av dem, eller hvis du skriver ut mange linjer uten å lese interaktorens svar. Programmet ditt får ikke åpne noen filer.

Interaksjonsprotokoll

Hele kommunikasjonsflyten er beskrevet nedenfor:

• Les den første linjen som inneholder to heltall $n$ og $k$ ($1 \le n, k \le 20$) — det er $n + 1$ nivåer, hvert med $k$ versjoner.
• Opptil $300\,000$ ganger, utfør en testgjennomspilling:
  • Skriv ut en linje på formen ? ver s (uten anførselstegn), der $\text{ver} \in [0, k - 1]$ og $s$ er en streng med $n$ bokstaver L og P. Flush.
  • Les neste linje som inneholder resultatet av gjennomspillingen — et heltall $x$ ($n \le x \le n \cdot 10^8 \le 2 \cdot 10^9$).
• Skriv ut en linje som inneholder ett enkelt tegn ! (utropstegn). Flush.
• Les neste linje som inneholder et heltall $q$ ($1 \le q \le 10\,000$) — antallet spørringer.
• For hver av de $q$ spørringene:
  • Les neste linje som inneholder et heltall $\text{ver}$ og en streng $s$ (samme grenser som ovenfor).
  • Skriv ut en linje som inneholder resultatet av gjennomspillingen (et heltall). Flush.

Illustrasjonen viser den første eksempeltesten ($n = 2; k = 4$). To avsluttende spørringer er markert med stiplede linjer: rozgrywka(0, "LL") $= 20 + 3 = 23$ og rozgrywka(1, "PL") $= 9 + 10 = 19$.

Eksempel

Her er et eksempel på kommunikasjonsflyt:

Merk

I vedlegget (du kan laste det ned i «attachment»-fanen på QOJ) finner du (feilaktige) eksempelløsninger G.cpp og G.py som utfører kommunikasjonen riktig, men beregner resultatene feil. Mappen inneholder også: en eksempelsjekker Gsoc.cpp og eksempeltester (G0a.in, G0b.in, G0c.in, samt en stor tilfeldig test G0d.in med $n = k = 20$). Formatet på testfilene er beskrevet i kommentaren i starten av Gsoc.cpp.

Eksempelsjekkeren Gsoc.cpp skiller seg fra den som brukes på QOJ. Den validerer muligens ikke inndata eller argumentene til gjennomspillingsfunksjonen.

Du kan kjøre løsningen din ved hjelp av skriptet run.sh. Kommandoen tar det kompilerte programmet og navnet på testfilen. For eksempel, for å kjøre eksempelprogrammene på eksempeltesten G0a.in:

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