Þetta er gagnvirkt verkefni.

Leikurinn „Pípulagningamaðurinn Mariusz“ (Plumber Mariusz) samanstendur af $n + 1$ borðum (númeruðum frá 0 til $n$), og hvert þeirra hefur $k$ útgáfur (númeraðar frá 0 til $k - 1$). Hver útgáfa hvers borðs (nema þess síðasta) endar á tveimur pípum — þeirri vinstri og þeirri hægri — og Mariusz verður að stökkva ofan í annað hvort þeirra. Hver pípa inniheldur einhvern fjölda mynta og leiðir í eina af útgáfum næsta borðs. Nákvæmlega tvær pípur leiða í hverja útgáfu hvers borðs (nema borðs núll); þetta geta verið hvaða tvær sem er af þeim $2 \cdot k$ pípum sem liggja út úr öllum $k$ útgáfum fyrra borðs.

Ein umferð felst í því að velja útgáfu af borði núll og velja síðan vinstri eða hægri pípu $n$ sinnum, og niðurstaða umferðarinnar er heildarfjöldi mynta sem safnast í pípunum $n$ sem farið var um. Við fáum ekki að vita hversu margar myntir voru í hverri pípu eða hvaða útgáfur borðanna voru heimsóttar. Myntirnar í pípunum endurstillast alltaf í upphafsgildi sín, þannig að allar umferðir eru óháðar. Því má tákna eina umferð með fallinu:

int rozgrywka(int ver, string s), þar sem $\text{ver} \in [0, k - 1]$ og $s$ er strengur af $n$ bókstöfum L og P.

Athugið að L og P samsvara pólsku orðunum yfir vinstri og hægri í sömu röð.

Þú mátt framkvæma allt að $300\,000$ prófunarumferðir og fá að vita niðurstöður þeirra. Eftir það færðu allt að $10\,000$ fyrirspurnir um umferðir. Verkefni þitt er að ákvarða niðurstöður þeirra.

Hvert próf er ákveðið áður en samskiptin hefjast (þ.e. gagnvirkniforritið er ekki aðlögunarhæft). Próf inniheldur stefnt vegið net með $(n + 1) \cdot k$ hnútum sem raðað er í $n + 1$ lög (borð), og $q$ fyrirspurnir $(\text{ver}, s)$. Hver hnútur (nema þeir í síðasta laginu) hefur tvo útleggi (vinstri og hægri), þar sem hver leggur er lýstur með myntafjölda $c \in [1, 10^8]$ og útgáfu $v \in [0, k - 1]$ sem hann leiðir til. Munið að sérhver hnútur nema þeir í lagi núll hefur inngráðu nákvæmlega 2.

Tæming biðminnis (Buffer flushing)

Eftir að hver lína er prentuð út verður þú að tæma úttaksbiðminnið (flush), svo að gagnvirkniforritið fái úttakslínuna. Til dæmis, í C++ geturðu prentað línu sem inniheldur upphrópunarmerki með cout << "!" << endl; eða með printf("!\n"); fflush(stdout);. Í Python geturðu notað print("!", flush=True). Við ábyrgjumst ekki stöðuga hegðun gagnvirkniforritsins ef þú prentar margar línur án þess að tæma biðminnið á eftir hverri þeirra, eða ef þú prentar margar línur án þess að lesa svör gagnvirkniforritsins. Forritið þitt má ekki opna neinar skrár.

Samskiptareglur

Heildarflæði samskiptanna er lýst hér að neðan:

• Lestu fyrstu línuna sem inniheldur tvær heiltölur $n$ og $k$ ($1 \le n, k \le 20$) — það eru $n + 1$ borð, hvert með $k$ útgáfur.
• Allt að $300\,000$ sinnum, framkvæmdu prófunarumferð:
  • Prentaðu línu á forminu ? ver s (án gæsalappa), þar sem $\text{ver} \in [0, k - 1]$ og $s$ er strengur af $n$ bókstöfum L og P. Tæmdu biðminnið (Flush).
  • Lestu næstu línu sem inniheldur niðurstöðu umferðarinnar — heiltölu $x$ ($n \le x \le n \cdot 10^8 \le 2 \cdot 10^9$).
• Prentaðu línu sem inniheldur eitt tákn ! (upphrópunarmerki). Tæmdu biðminnið (Flush).
• Lestu næstu línu sem inniheldur heiltölu $q$ ($1 \le q \le 10\,000$) — fjölda fyrirspurna.
• Fyrir hverja af $q$ fyrirspurnunum:
  • Lestu næstu línu sem inniheldur heiltölu $\text{ver}$ og streng $s$ (sömu mörk og að ofan).
  • Prentaðu línu sem inniheldur niðurstöðu umferðarinnar (heiltölu). Tæmdu biðminnið (Flush).

Myndin sýnir fyrsta sýnidæmið ($n = 2; k = 4$). Tvær lokafyrirspurnir eru merktar með brotalínum: rozgrywka(0, "LL") $= 20 + 3 = 23$ og rozgrywka(1, "PL") $= 9 + 10 = 19$.

Dæmi

Hér er dæmi um samskiptaflæði:

Athugasemd

Í viðhenginu (þú getur sótt það í flipanum „attachment“ á QOJ) finnurðu (rangar) sýnilausnir G.cpp og G.py sem framkvæma samskiptin rétt, en reikna niðurstöðurnar rangt. Mappan inniheldur einnig: sýniyfirlesara Gsoc.cpp og sýnipróf (G0a.in, G0b.in, G0c.in, og stórt slembipróf G0d.in með $n = k = 20$). Sniði prófunarskránna er lýst í athugasemd fremst í Gsoc.cpp.

Sýniyfirlesarinn Gsoc.cpp er ólíkur þeim sem notaður er á QOJ. Hann sannreynir hugsanlega ekki inntakið eða viðföng umferðarfallsins.

Þú getur keyrt lausnina þína með skriftunni run.sh. Skipunin tekur þýdda forritið og nafn prófunarskrárinnar. Til dæmis, til að keyra sýniforritin á sýniprófinu G0a.in:

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