2. Ako sa časy menia

Píše sa 31. jún 2019. Prešlo už viac ako 20 rokov odkedy ste nezískali tender na napísanie programu pre jadrovú elektráreň na matfyze. Ale časy sa menia a tentoraz je šťastie na vašej strane. Ministerstvo Krajne Serióznych Projektov sa rozhodlo vykonať rutinnú 20 ročnú kontrolu bezpečnostných systémov kritických zariadení republiky a vy ste vyhrali tento tender! Hlava sa vám točí nad predstavou koľko korniet si budete vedieť kúpiť. Ale najprv práca, potom kornetá, hor sa do roboty!

Bezpečnostný systém funguje na báze Masívneho hesla, teda číselnej kombinácie, ktoré má uložené v pamäti a ktoré porovnáva s pokusmi od užívateľa. Vám však netrvalo dlho zistiť, že to kódil naozaj iba nejaký skoro-programátor. Pokus sa vyhodnotí ako nesprávny nie keď sa zadané heslo nezhoduje s Masívnym heslom, ale keď obsahuje nejaké znaky navyše! To znamená, že na poradí znakov v hesle vôbec nezáleží a že napríklad prázdne heslo bude vždy správne.

Ministerstvo nebolo veľmi nadšené vaším zistením, ale odľahlo im, lebo vraj potenciálny útočník túto chybu nevedel použiť na zistenie Masívneho hesla. To totižto používajú úplne všade a ak by ho zistiť vedel, bola by šanca, že ho niekedy v minulosti získal alebo možno v blízkej budúcnosti získa. Toto by nemohli riskovať, museli by Masívne heslo všade zmeniť a komu sa to chce.

Dokážte, že sa mýlia a že sa táto chyba dá použiť na zistenie Masívneho hesla. Navrhnite program, ktorý toto Masívne heslo nájde.

Úloha

Táto úloha je interaktívna. Namiesto kompletného vstupu budete dostávať odpovede na vaše otázky. Heslo je podmnožina, teda niekoľko rôznych celých čísel od \(1\) po \(N\), pričom Masívne heslo má dĺžku najviac \(M\) čísel.

Vaša otázka je tip na Masívne heslo. Odpoveď na vašu otázku bude kladná, pokiaľ je každý jeden prvok tejto otázky súčasťou Masívneho hesla. Teda otázka bude vyhodnotená záporne, pokiaľ obsahuje aspoň jeden prvok, ktorý nie je súčasťou Masívneho hesla. Vašou úlohou je zistiť Masívne heslo.

Môžete sa opýtať nanajvýš \(111\,111\) otázok.

Formát vstupu

Na prvom riadku dostanete čísla \(N\) – najväčšie možné číslo v hesle a \(M\) – maximálnu dĺžku Masívneho hesla, pri čom vždy platí \((0 \leq M \leq N \leq 10^5)\).

Následne dostanete odpoveď na každú vašu otázku jedným riadkom obsahujúcim JOP v prípade kladného vyhodnotenia a NOP v prípade záporného.

Formát výstupu

Každá otázka, ktorú položíte, by mala byť vypísaná na jednom novom riadku. Riadok sa začína číslom \(K\) - dĺžkou hesla. Za ním nasleduje medzera a \(K\) medzerou oddelených čísel – vaša otázka. V prípade, že si myslíte, že poznáte Masívne heslo, vypíšte -1 a na nový riadok vypíšte toto heslo v rovnakom formáte, ako otázky (teda číslo \(K\) a za ním \(K\) medzerou oddelených čísel).

Pokiaľ sa opýtate viac ako \(111\,111\) otázok, váš program bude nemilosrdne ukončený a v testovači sa to prejaví verdiktom "WA - Zlá odpoveď" alebo dokonca "EXC - Chyba počas behu programu".

Flushovanie

Programovacie jazyky štandardne používajú výstupný buffer, a až po jeho zaplnení program vypíše jeho obsah. Flushovanie vlastne znamená vypísanie (vyprázdnenie) tohto buffera. Vždy, keď vypíšete svoju otázku, musíte ešte flushnúť výstupný buffer. Inak sa váš ťah v skutočnosti nevypíše a nedostane sa k nášmu programu. V konečnom dôsledku potom dostanete hlášku "TLE - Prekročený časový limit".

Ako flushovať?

Ak programujete v C/C++ a používate printf(), na to aby ste flushli jeho buffer, použite fflush(stdout). Ak používate cout, buffer sa flushuje automaticky po vypísaní konca riadku pomocou cout<<endl. Ak programujete v Pythone, používajte print(vystup, flush=True). Ak programujete v Pascale použite flush(output).

Hodnotenie

Sú 4 testovacie sady, každá za 2 body. Platia v nich nasledovné obmedzenia:

Navyše v druhej sade platí, že počet platných tajných hesiel je malý, teda hesiel ktoré neporušujú obmedzenie na maximálnu veľkosť Masívneho hesla.

V hodnotení popisu sa bude samozrejme klásť veľký dôraz na časovú zložitosť, ale tento krát ešte väčší na počet položených otázok. Odhad počtu položených otázok a časovej zložitosti programu nezabudnite zdôvodniť a dokázať.

Príklad

>>>3 2
0
>>>JOP
2 1 2
>>>NOP
2 1 3
>>>NOP
2 2 3
>>>JOP
-1
2 2 3

Pre lepšiu čitateľnosť sme pred riadky obsahujúce výstup testovača dopísali prompt ">>>". Tento sa v skutočnosti nikde nezjaví: ani náš program ho nevypíše, ani vy ho nemáte vypisovať.