Þetta er gagnvirkt verkefni.

Little Cyan Fish á falið einfalt óstefnt net með $n$ hnútum, sem eru númeraðir frá $1$ til $n$. Þú veist gildið á $n$, en þú þekkir engan af leggjunum. Little Cyan Fish heldur mikið upp á hugtakið snið (cut). Fyrir mengi hnúta $S$, látum $\operatorname{cut}(S)$ tákna fjölda leggja sem hafa nákvæmlega annan endapunktinn í $S$.

Little Cyan Fish leyfir þér að bera saman snið með því að gera fyrirspurnir. Í einni fyrirspurn velur þú tvö mengi hnúta $S_1$ og $S_2$. Little Cyan Fish segir þér hvort $\operatorname{cut}(S_1)$ sé minna en, jafnt og, eða stærra en $\operatorname{cut}(S_2)$.

Þú getur líklega giskað á að næst verði talað um að endurgera netið, en í þetta sinn er verkefnið auðveldara. Little Cyan Fish gefur þér hnút $u$, og hann vill að þú finnir alla hnúta sem eru aðlægir $u$ í mesta lagi $n + 10$ fyrirspurnum.

Inntak

Fyrsta línan í inntakinu inniheldur tvær heiltölur $n$ og $u$ ($1 \le n \le 1000$, $1 \le u \le n$), sem tákna fjölda hnúta og gefna hnútinn, í sömu röð. Síðan hefst samskiptaferlið.

Samskiptareglur

Til að gera fyrirspurn skaltu prenta línu á eftirfarandi sniði:

$$?\ s_1\ s_2$$

þar sem $s_1$ og $s_2$ eru strengir af lengd $n$, sem samanstanda eingöngu af stöfunum 0 og 1. Fyrir hvert $j \in \{1, 2\}$ tilheyrir hnútur $i$ menginu $S_j$ þá og því aðeins að $i$-ti stafurinn í $s_j$ sé 1. Mengin mega vera tóm, mega skarast og mega vera jöfn.

Sem svar við fyrirspurninni færðu einn staf <, =, eða >, sem þýðir að $\operatorname{cut}(S_1)$ er minna en, jafnt og, eða stærra en $\operatorname{cut}(S_2)$, í sömu röð. Þú verður að tryggja að fjöldi fyrirspurna sem þú gerir fari ekki yfir $n + 10$.

Til að tilkynna svarið skaltu prenta línu á eftirfarandi sniði:

$$!\ k\ v_1\ v_2\ \dots\ v_k$$

þar sem $k$ ($0 \le k \le n - 1$) er fjöldi hnúta sem eru aðlægir $u$, og $v_1, v_2, \ldots, v_k$ eru ólík númer þeirra í hvaða röð sem er. Ef $k = 0$ skaltu prenta ! 0. Að tilkynna svarið telst ekki sem fyrirspurn. Forritið þitt verður að hætta keyrslu strax eftir að svarið hefur verið tilkynnt.

Eftir að hafa prentað fyrirspurn eða tilkynnt svarið skaltu ekki gleyma að prenta nýlínustaf og tæma úttaksbiðminnið (flush). Ef þú gerir ógilda fyrirspurn eða ferð yfir hámarksfjölda fyrirspurna mun samskiptaforritið (interactor) loka inntaksstraumnum og forritið þitt verður að hætta keyrslu.

Í þessu verkefni er samskiptaforritið aðlögunarhæft (adaptive). Þetta þýðir að netið getur breyst eftir fyrirspurnum þínum, svo lengi sem það stangast ekki á við nein fyrri svör. Svarið þitt verður að vera rétt fyrir hvert net sem samræmist öllum svörum sem þú hefur fengið.

Dæmi

Inntak 1

4 1

<

=

<

=

Úttak 1

? 0000 1000

? 0100 1100

? 0010 1010

? 0001 1001

! 2 2 4

Athugasemd

Eitt net sem samræmist samskiptunum í dæminu hefur leggina $(1, 2)$, $(1, 4)$ og $(2, 3)$.

Prófunartól: Prófunartól er lagt til svo keppendur geti þróað og prófað lausnir sínar. Þú getur sótt þetta tól úr viðhengjunum. Keyrðu tólið með valkostinum -h til að birta notkunarleiðbeiningar. Tólið prófar samskiptin og tilkynnta svarið, en framfylgir hvorki tíma- né minnistakmörkunum.

Prófunartólið notar fast net sem tilgreint er í inntaksskrá þess í gegnum öll samskiptin, á meðan opinbera samskiptaforritið er aðlögunarhæft. Að standast prófanir með prófunartólinu tryggir ekki að lausnin þín sé rétt gegn opinbera samskiptaforritinu.