Бұл интерактивті есеп.

«Су құбыршысы Мариуш» (Plumber Mariusz) ойыны $n + 1$ деңгейден (0-ден $n$-ге дейін нөмірленген) тұрады, олардың әрқайсысының $k$ нұсқасы (0-ден $k - 1$-ге дейін нөмірленген) бар. Әр деңгейдің әрбір нұсқасы (соңғысынан басқа) екі құбырмен — сол жақ және оң жақ құбырмен — аяқталады, ал Мариуш олардың біріне секіруі тиіс. Әр құбырда бірнеше тиын бар және ол келесі деңгейдің нұсқаларының біріне апарады. (Нөлдік деңгейден басқа) әр деңгейдің әрбір нұсқасына дәл екі құбыр апарады; бұлар алдыңғы деңгейдің барлық $k$ нұсқасынан шығатын $2 \cdot k$ құбырдың ішіндегі кез келген екеуі болуы мүмкін.

Бір ойын өтуі нөлдік деңгейдің бір нұсқасын таңдап, содан кейін $n$ рет сол немесе оң жақ құбырды таңдаудан тұрады, ал ойынның нәтижесі — кіріп шыққан $n$ құбырда жиналған тиындардың жалпы саны. Біз әр құбырда қанша тиын болғанын немесе деңгейлердің қандай нұсқаларына кіргенімізді білмейміз. Құбырлардағы тиындар әрдайым бастапқы мәндеріне қайта оралады, сондықтан барлық ойын өтулері өзара тәуелсіз. Олай болса, бір ойын өтуін келесі функциямен сипаттауға болады:

int rozgrywka(int ver, string s), мұндағы $\text{ver} \in [0, k - 1]$, ал $s$ — $n$ әріптен (L және P) тұратын жол.

Назар аударыңыз, L және P сәйкесінше поляк тіліндегі сол және оң деген сөздерге сәйкес келеді.

Сіз $300\,000$ ретке дейін сынақ ойындарын жүргізіп, олардың нәтижелерін біле аласыз. Одан кейін сізге ойындар туралы $10\,000$-ға дейін сұраным беріледі. Сіздің міндетіңіз — олардың нәтижелерін анықтау.

Әрбір тест өзара әрекеттесу басталғанға дейін бекітілген (яғни интерактор бейімделгіш емес). Тест $n + 1$ қабатқа (деңгейге) орналасқан $(n + 1) \cdot k$ төбесі бар бағытталған салмақты графтан және $q$ сұранымнан $(\text{ver}, s)$ тұрады. Соңғы қабаттағы төбелерден басқа әрбір төбенің екі шығыс қыры (сол және оң) бар, олардың әрқайсысы $c \in [1, 10^8]$ тиын санымен және ол апаратын $v \in [0, k - 1]$ нұсқасымен сипатталады. Нөлдік қабаттағы төбелерден басқа барлық төбелердің кіріс дәрежесі дәл 2-ге тең екенін еسكеріңіз.

Буферді тазарту (Buffer flushing)

Әрбір жолды шығарғаннан кейін шығыс буферін тазартуыңыз (flush) керек, сонда интерактор шығарылған жолды қабылдай алады. Мысалы, C++ тілінде леп белгісі бар жолды cout << "!" << endl; немесе printf("!\n"); fflush(stdout); арқылы шығаруға болады. Python тілінде print("!", flush=True) қолдануға болады. Егер сіз әр жолдан кейін буферді тазартпай бірнеше жол шығарсаңыз немесе интерактордың жауаптарын оқымай көп жол шығарсаңыз, интерактордың тұрақты жұмысына кепілдік берілмейді. Бағдарламаңыз ешқандай файлдарды ашпауы тиіс.

Өзара әрекеттесу хаттамасы

Толық байланыс барысы төменде сипатталған:

• Екі бүтін саннан $n$ және $k$ ($1 \le n, k \le 20$) тұратын бірінші жолды оқыңыз — барлығы $n + 1$ деңгей бар, әрқайсысының $k$ нұсқасы бар.
• Ең көбі $300\,000$ рет сынақ ойынын орындаңыз:
  • ? ver s түріндегі жолды (тырнақшасыз) шығарыңыз, мұндағы $\text{ver} \in [0, k - 1]$ және $s$ — $n$ әріптен (L және P) тұратын жол. Буферді тазартыңыз.
  • Ойын нәтижесін — бүтін $x$ ($n \le x \le n \cdot 10^8 \le 2 \cdot 10^9$) санын қамтитын келесі жолды оқыңыз.
• Жалғыз ! (леп белгісі) таңбасынан тұратын жолды шығарыңыз. Буферді тазартыңыз.
• Сұранымдар санын білдіретін бүтін $q$ ($1 \le q \le 10\,000$) саны бар келесі жолды оқыңыз.
• $q$ сұранымның әрқайсысы үшін:
  • Бүтін $\text{ver}$ саны мен $s$ жолы бар келесі жолды оқыңыз (шектеулер жоғарыдағыдай).
  • Ойын нәтижесін (бүтін санды) қамтитын жолды шығарыңыз. Буферді тазартыңыз.

Суретте бірінші үлгі тест ($n = 2; k = 4$) көрсетілген. Соңғы екі сұраным үзік сызықтармен белгіленген: rozgrywka(0, "LL") $= 20 + 3 = 23$ және rozgrywka(1, "PL") $= 9 + 10 = 19$.

Мысал

Төменде байланыс барысының мысалы келтірілген:

Ескертпе

Тіркемеден (оны QOJ сайтындағы «attachment» қойындысынан жүктеп алуға болады) байланысты дұрыс орындайтын, бірақ нәтижелерді қате есептейтін үлгі (қате) шешімдерді G.cpp және G.py таба аласыз. Сондай-ақ каталогта: үлгі тексеруші Gsoc.cpp және үлгі тесттер (G0a.in, G0b.in, G0c.in және $n = k = 20$ болатын үлкен кездейсоқ тест G0d.in) бар. Тест файлдарының пішімі Gsoc.cpp файлының басындағы түсініктемеде сипатталған.

Үлгі тексеруші Gsoc.cpp QOJ-да қолданылатын тексерушіден өзгеше. Ол кіріс деректерді немесе ойын функциясының аргументтерін тексермеуі мүмкін.

Шешіміңізді run.sh скрипті арқылы іске қоса аласыз. Команда компиляцияланған бағдарламаны және тест файлының атауын қабылдайды. Мысалы, G0a.in үлгі тестінде үлгі бағдарламаларды іске қосу үшін:

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