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

Little Cyan Fish-те $1$-ден $n$-ге дейін нөмірленген $n$ төбесі бар жасырын қарапайым бағытталмаған граф бар. Сіз $n$ мәнін білесіз, бірақ ешбір қырын білмейсіз. Little Cyan Fish қима (cut) ұғымын өте жақсы көреді. Төбелердің $S$ жиыны үшін $\operatorname{cut}(S)$ арқылы дәл бір ұшы $S$-те жататын қырлар санын белгілейік.

Little Cyan Fish сұраныстар жасау арқылы қималарды салыстыруға мүмкіндік береді. Бір сұраныста сіз екі төбелер жиынын — $S_1$ және $S_2$ таңдайсыз. Little Cyan Fish сізге $\operatorname{cut}(S_1)$ мәні $\operatorname{cut}(S_2)$ мәнінен кіші, оған тең немесе одан үлкен екенін айтады.

Келесі сөйлем графты қалпына келтіру туралы болатынын болжаған шығарсыз, бірақ бұл жолы тапсырма оңайырақ. Little Cyan Fish сізге $u$ төбесін береді және сізден ең көбі $n + 10$ сұраныс ішінде $u$ төбесімен көршілес барлық төбелерді табуды қалайды.

Кіріс деректер

Кіріс деректердің бірінші жолында сәйкесінше төбелер санын және берілген төбені білдіретін екі бүтін сан $n$ және $u$ ($1 \le n \le 1000$, $1 \le u \le n$) берілген. Содан кейін өзара әрекеттесу басталады.

Өзара әрекеттесу протоколы

Сұраныс жасау үшін келесі форматта бір жол шығарыңыз:

$$?\ s_1\ s_2$$

мұндағы $s_1$ және $s_2$ — тек 0 және 1 таңбаларынан тұратын, ұзындығы $n$ болатын жолдар. Әрбір $j \in \{1, 2\}$ үшін, $i$ төбесі $S_j$ жиынына тек және тек $s_j$ жолының $i$-ші таңбасы 1 болғанда ғана тиісті болады. Жиындар бос болуы, қиылысуы және өзара тең болуы мүмкін.

Сұранысқа жауап ретінде сіз сәйкесінше $\operatorname{cut}(S_1)$ мәні $\operatorname{cut}(S_2)$ мәнінен кіші, оған тең немесе одан үлкен екенін білдіретін жалғыз <, = немесе > таңбасын аласыз. Сіз жасаған сұраныстар саны $n + 10$-нан аспайтынына кепілдік беруіңіз керек.

Жауапты хабарлау үшін келесі форматта бір жол шығарыңыз:

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

мұндағы $k$ ($0 \le k \le n - 1$) — $u$ төбесімен көршілес төбелер саны, ал $v_1, v_2, \ldots, v_k$ — олардың кез келген реттегі әртүрлі нөмірлері. Егер $k = 0$ болса, ! 0 шығарыңыз. Жауапты хабарлау сұраныс ретінде есептелмейді. Жауапты хабарлағаннан кейін бағдарламаңыз бірден жұмысын аяқтауы тиіс.

Сұранысты шығарғаннан кейін немесе жауапты хабарлағаннан кейін жаңа жол таңбасын шығаруды және шығыс ағынын тазартуды (flush) ұмытпаңыз. Егер сіз жарамсыз сұраныс жасасаңыз немесе сұраныстар шегінен асып кетсеңіз, интерактивті тексеруші (interactor) кіріс ағынын жабады және бағдарламаңыз жұмысын тоқтатуы тиіс.

Бұл есепте интерактивті тексеруші бейімделгіш (adaptive) болып табылады. Бұл дегеніміз — граф алдыңғы жауаптардың ешқайсысына қайшы келмейтіндей етіп, сіздің сұраныстарыңызға байланысты өзгеруі мүмкін. Сіздің жауабыңыз сіз алған барлық жауаптармен үйлесетін кез келген граф үшін дұрыс болуы керек.

Мысалдар

Кіріс деректер 1

4 1

<

=

<

=

Шығыс деректер 1

? 0000 1000

? 0100 1100

? 0010 1010

? 0001 1001

! 2 2 4

Ескертпе

Мысалдағы өзара әрекеттесумен үйлесетін графтардың бірінде $(1, 2)$, $(1, 4)$ және $(2, 3)$ қырлары бар.

Тестілеу құралы: Қатысушыларға өз шешімдерін әзірлеуге және тексеруге көмектесу үшін тестілеу құралы ұсынылады. Бұл құралды тіркемелерден жүктеп алуға болады. Пайдалану нұсқауларын көрсету үшін құралды -h опциясымен іске қосыңыз. Құрал өзара әрекеттесуді және хабарланған жауапты тексереді, бірақ уақыт немесе жад шектеулерін қадағаламайды.

Тестілеу құралы бүкіл өзара әрекеттесу барысында өзінің кіріс файлында көрсетілген бекітілген графты пайдаланады, ал ресми интерактивті тексеруші бейімделгіш болып табылады. Тестілеу құралымен тестілерден өту шешіміңіздің ресми интерактивті тексерушіге қарсы дұрыс екеніне кепілдік бермейді.