Tämä on vuorovaikutteinen tehtävä.

Peli ”Putkimies Mariusz” (Plumber Mariusz) koostuu $n + 1$ tasosta (numeroitu 0 – $n$), joista jokaisella on $k$ versiota (numeroitu 0 – $k - 1$). Jokaisen tason jokainen versio (viimeistä tasoa lukuun ottamatta) päättyy kahteen putkeen — vasempaan ja oikeaan — ja Mariuszin on hypättävä jompaankumpaan niistä. Jokaisessa putkessa on tietty määrä kolikoita, ja putki johtaa johonkin seuraavan tason versioista. Täsmälleen kaksi putkea johtaa jokaisen tason jokaiseen versioon (tasoa nolla lukuun ottamatta); nämä voivat olla mitkä tahansa kaksi edellisen tason kaikista $k$ versiosta lähtevän $2 \cdot k$ putken joukosta.

Yksi pelikerta koostuu tason nolla version valitsemisesta ja sen jälkeen vasemman tai oikean putken valitsemisesta $n$ kertaa, ja pelikerran tulos on käydyissä $n$ putkessa kerättyjen kolikoiden kokonaismäärä. Emme saa tietää, kuinka monta kolikkoa kussakin putkessa oli tai missä tasojen versioissa vierailtiin. Putkissa olevat kolikot palautuvat aina alkuarvoihinsa, joten kaikki pelikerrat ovat toisistaan riippumattomia. Pelikerta voidaan siten esittää funktiolla:

int rozgrywka(int ver, string s), missä $\text{ver} \in [0, k - 1]$ ja $s$ on $n$ kirjaimesta L ja P koostuva merkkijono.

Huomaa, että L ja P vastaavat puolan kielen sanoja vasen ja oikea.

Voit suorittaa enintään $300\,000$ testipelikertaa ja saada tietää niiden tulokset. Tämän jälkeen saat enintään $10\,000$ kyselyä pelikerroista. Tehtäväsi on selvittää niiden tulokset.

Jokainen testi on kiinnitetty ennen vuorovaikutuksen alkua (eli interaktori ei ole mukautuva). Testi sisältää suunnatun painotetun verkon, jossa on $(n + 1) \cdot k$ solmua järjestettynä $n + 1$ kerrokseen (tasoon), sekä $q$ kyselyä $(\text{ver}, s)$. Jokaisesta solmusta (viimeisen kerroksen solmuja lukuun ottamatta) lähtee kaksi kaarta (vasen ja oikea), joista kumpikin kuvataan kolikkomäärällä $c \in [1, 10^8]$ ja kohdeversiolla $v \in [0, k - 1]$, johon se johtaa. Muista, että jokaisen solmun (kerroksen nolla solmuja lukuun ottamatta) tuloaste on täsmälleen 2.

Puskurin tyhjennys (Buffer flushing)

Jokaisen rivin tulostamisen jälkeen sinun on tyhjennettävä tulostuspuskuri (flush), jotta interaktori vastaanottaa tulostetun rivin. Esimerkiksi C++:ssa voit tulostaa huutomerkin sisältävän rivin komennolla cout << "!" << endl; tai printf("!\n"); fflush(stdout);. Pythonissa voit käyttää komentoa print("!", flush=True). Emme takaa interaktorin vakaata toimintaa, jos tulostat useita rivejä tyhjentämättä puskuria jokaisen jälkeen tai jos tulostat monta riviä lukematta interaktorin vastauksia. Ohjelmasi ei saa avata mitään tiedostoja.

Vuorovaikutusprotokolla

Koko viestintäkulku on kuvattu alla:

• Lue ensimmäinen rivi, joka sisältää kaksi kokonaislukua $n$ ja $k$ ($1 \le n, k \le 20$) — tasoja on $n + 1$ ja kullakin $k$ versiota.
• Suorita enintään $300\,000$ kertaa testipelikerta:
  • Tulosta muotoa ? ver s oleva rivi (ilman lainausmerkkejä), missä $\text{ver} \in [0, k - 1]$ ja $s$ on $n$ kirjaimesta L ja P koostuva merkkijono. Tyhjennä puskuri (Flush).
  • Lue seuraava rivi, joka sisältää pelikerran tuloksen — kokonaisluvun $x$ ($n \le x \le n \cdot 10^8 \le 2 \cdot 10^9$).
• Tulosta rivi, joka sisältää yhden merkin ! (huutomerkki). Tyhjennä puskuri (Flush).
• Lue seuraava rivi, joka sisältää kokonaisluvun $q$ ($1 \le q \le 10\,000$) — kyselyiden lukumäärän.
• Jokaiselle $q$ kyselystä:
  • Lue seuraava rivi, joka sisältää kokonaisluvun $\text{ver}$ ja merkkijonon $s$ (samat rajoitukset kuin yllä).
  • Tulosta rivi, joka sisältää pelikerran tuloksen (kokonaisluvun). Tyhjennä puskuri (Flush).

Kuva esittää ensimmäistä esimerkkitestiä ($n = 2; k = 4$). Kaksi lopullista kyselyä on merkitty katkoviivoin: rozgrywka(0, "LL") $= 20 + 3 = 23$ ja rozgrywka(1, "PL") $= 9 + 10 = 19$.

Esimerkki

Tässä on esimerkki viestintäkulusta:

Huomautus

Liitteestä (voit ladata sen QOJ:n ”attachment”-välilehdeltä) löydät (virheelliset) esimerkkiratkaisut G.cpp ja G.py, jotka hoitavat viestinnän oikein, mutta laskevat tulokset väärin. Hakemisto sisältää myös: esimerkkitarkistimen Gsoc.cpp ja esimerkkitestit (G0a.in, G0b.in, G0c.in sekä suuren satunnaistestin G0d.in, jossa $n = k = 20$). Testitiedostojen muoto on kuvattu Gsoc.cpp-tiedoston alussa olevassa kommentissa.

Esimerkkitarkistin Gsoc.cpp poikkeaa QOJ:ssa käytettävästä tarkistimesta. Se ei välttämättä tarkista syötettä tai pelikertafunktion argumentteja.

Voit ajaa ratkaisusi skriptillä run.sh. Komento ottaa parametrinaan käännetyn ohjelman ja testitiedoston nimen. Esimerkiksi esimerkkiohjelmien ajaminen esimerkkitestillä G0a.in:

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