Dette er en interaktiv oppgave.

Little Cyan Fish har en skjult enkel urettet graf med $n$ noder, nummerert fra $1$ til $n$. Du kjenner verdien av $n$, men du kjenner ikke til noen av kantene. Little Cyan Fish elsker begrepet snitt (cut). For en mengde noder $S$, la $\operatorname{cut}(S)$ betegne antallet kanter som har nøyaktig ett endepunkt i $S$.

Little Cyan Fish lar deg sammenligne snitt ved å stille spørsmål. I ett spørsmål velger du to mengder av noder $S_1$ og $S_2$. Little Cyan Fish forteller deg om $\operatorname{cut}(S_1)$ er mindre enn, lik eller større enn $\operatorname{cut}(S_2)$.

Du kan sannsynligvis gjette at neste setning vil handle om å gjenoppbygge grafen, men denne gangen er oppgaven enklere. Little Cyan Fish gir deg en node $u$, og han vil at du skal finne alle noder som er naboer til $u$ med høyst $n + 10$ spørsmål.

Inndata

Den første linjen i inndataene inneholder to heltall $n$ og $u$ ($1 \le n \le 1000$, $1 \le u \le n$), som angir henholdsvis antallet noder og den oppgitte noden. Deretter starter interaksjonen.

Interaksjonsprotokoll

For å stille et spørsmål, skriv ut en linje på følgende format:

$$?\ s_1\ s_2$$

der $s_1$ og $s_2$ er strenger med lengde $n$, som kun består av tegnene 0 og 1. For hver $j \in \{1, 2\}$ tilhører noden $i$ mengden $S_j$ hvis og bare hvis det $i$-te tegnet i $s_j$ er 1. Mengdene kan være tomme, kan overlappe og kan være like.

Som svar på spørsmålet vil du få ett enkelt tegn <, =, eller >, som betyr at $\operatorname{cut}(S_1)$ er henholdsvis mindre enn, lik eller større enn $\operatorname{cut}(S_2)$. Du må sørge for at antallet spørsmål du stiller ikke overstiger $n + 10$.

For å rapportere svaret, skriv ut en linje på følgende format:

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

der $k$ ($0 \le k \le n - 1$) er antallet noder som er naboer til $u$, og $v_1, v_2, \ldots, v_k$ er deres distinkte numre i hvilken som helst rekkefølge. Hvis $k = 0$, skriv ut ! 0. Å rapportere svaret telles ikke som et spørsmål. Programmet ditt må avsluttes umiddelbart etter at svaret er rapportert.

Etter å ha skrevet ut et spørsmål eller rapportert svaret, må du ikke glemme å skrive ut et linjeskifttegn og tømme utdatabufferen (flush). Hvis du stiller et ugyldig spørsmål eller overskrider spørsmålsgrensen, vil interaktoren lukke inndatastrømmen og programmet ditt må avsluttes.

I denne oppgaven er interaktoren adaptiv. Dette betyr at grafen kan endre seg avhengig av spørsmålene dine, så lenge den ikke motsier noen tidligere svar. Svaret ditt må være riktig for enhver graf som er konsistent med alle svarene du har mottatt.

Eksempler

Inndata 1

4 1

<

=

<

=

Utdata 1

? 0000 1000

? 0100 1100

? 0010 1010

? 0001 1001

! 2 2 4

Forklaring

Én graf som er konsistent med eksempelinteraksjonen har kantene $(1, 2)$, $(1, 4)$ og $(2, 3)$.

Testverktøy: Et testverktøy er tilgjengelig for å hjelpe deltakerne med å utvikle og teste løsningene sine. Du kan laste ned dette verktøyet fra vedleggene. Kjør verktøyet med valget -h for å vise bruksinstruksjoner. Verktøyet sjekker interaksjonen og det rapporterte svaret, men håndhever ikke tids- eller minnegrensen.

Testverktøyet bruker en fast graf spesifisert i inndatafilen gjennom hele interaksjonen, mens den offisielle interaktoren er adaptiv. Å bestå tester med testverktøyet garanterer ikke at løsningen din er riktig mot den offisielle interaktoren.