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

KUPC-кун келесі есепті шығаратын бағдарлама жазды.

Сізге $N$ төбесі бар $T = (V, E)$ ағашы берілген. $T$ ағашының төбелерінен тұратын ұзындығы $k$ болатын $\{a_1, \dots, a_k\}$ тізбегі үшін оның ұпайын келесідей анықтайық. - $d(u, v)$ арқылы $T$ ағашындағы $u$ мен $v$ төбелерінің арасындағы жолдағы қабырғалар санын белгілейік. Сонда ұпай $\prod_{i=1}^k d(a_i, a_{(i \bmod k)+1})$ болады.

$V$ жиынының $S$ ішкі жиыны берілген. Әрбір $1 \le k \le N$ үшін келесі $q_k$ мәнін табыңыз. - Элементтері $S$ жиынына тиісті, ұзындығы $k$ болатын барлық $\{a_1, \dots, a_k\}$ төбелер тізбектерінің ұпайларының қосындысы ($2^{61} - 1$ модулі бойынша).

KUPC-кун $T$ ағашы туралы ақпаратты алдын ала құпия сақтайды және бағдарламаға берілетін ағаш ретінде $T$-ны қолдануды жалғастырады.

Сіз жоғарыдағы бағдарламаны пайдаланып, жапырақтар туралы ақпаратты қалпына келтіруге тырысасыз. Ағаштың төбелер саны $N$ болса, сіз келесі сұрақты ең көбі $N$ рет қоя аласыз.

• $V$ жиынының $S$ ішкі жиынын таңдап, бағдарламаның шығысын сұрау.

KUPC-кунның бағдарламасы дұрыс деп есептеп, сұрақтар арқылы алынған ақпараттан $T$ ағашындағы барлық жапырақтарды анықтаңыз.

Қазылар алқасы бейімделгіш емес (not adaptive), яғни $T$ ағашы өзара әрекеттесу басталғанға дейін бекітілген.

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

Алдымен стандартты кірістен $N$ беріледі. ($2 \le N \le 50$)

Әрбір сұрақ үшін стандартты шығысқа келесі форматта шығарыңыз.

? s1s2...sN

Мұндағы $s_1s_2\cdots s_N$ — $S$ ішкі жиынын сипаттайтын ұзындығы $N$ жол, мұнда егер $i \in S$ болса, $s_i = 1$, ал егер $i \notin S$ болса, $s_i = 0$.

Жауап ретінде стандартты кірістен келесі деректер беріледі.

q1 q2 ... qN

Барлық жапырақтарды анықтағаннан кейін, жауабыңызды келесі форматта шығарыңыз.

! t1t2...tN

Мұндағы $t_1t_2\cdots t_N$ — ұзындығы $N$ жол, мұнда егер $i$ жапырақ болса, $t_i = 1$, ал жапырақ болмаса, $t_i = 0$.

Осы шығыстан кейін бағдарламаңызды дереу аяқтаңыз.

Бірдеңе шығарған сайын соңына жаңа жол таңбасын қосып, стандартты шығыс буферін тазалаңыз (flush).

Мысал

1-мысал кірісі

5

0 8 0 32 0

0 44 108 968 3960

0 0 0 0 0

0 76 348 3336 22200

1-мысал шығысы

? 00101

? 11001

? 10000

? 11111

! 11001

Ескертпе

Бірінші мысал үшін қазылар алқасы құпия сақтайтын ағаштың қабырғалар жиыны: $(1, 3), (2, 3), (3, 4), (4, 5)$.

Бірінші сұрақта $S = \{3, 5\}$.

$d(3, 3) = 0, d(3, 5) = d(5, 3) = 2, d(5, 5) = 0$ екеніне назар аударыңыз.

Мысалы, элементтері $S$-ке тиісті, ұзындығы $2$ болатын келесі $4$ төбелер тізбегі $a$ бар.

• Егер $a = (3, 3)$ болса, онда бұл тізбектің ұпайы $d(3, 3) \times d(3, 3) = 0 \times 0 = 0$.
• Егер $a = (3, 5)$ болса, онда бұл тізбектің ұпайы $d(3, 5) \times d(5, 3) = 2 \times 2 = 4$.
• Егер $a = (5, 3)$ болса, онда бұл тізбектің ұпайы $d(5, 3) \times d(3, 5) = 2 \times 2 = 4$.
• Егер $a = (5, 5)$ болса, онда бұл тізбектің ұпайы $d(5, 5) \times d(5, 5) = 0 \times 0 = 0$.

Қазылар алқасы $q_2$ үшін $8$ деп жауап береді, бұл — $0 + 4 + 4 + 0$ қосындысын $2^{61} - 1$ санына бөлгендегі қалдық.

Басқа тізбек ұзындықтары үшін де дәл осылай есептеу арқылы қазылар алқасының 0 8 0 32 0 жауабын аламыз.

Бұл ағаштың жапырақтары — $1, 2, 5$ төбелері, сондықтан ! 11001 шығару жапырақтарды анықтауды дұрыс аяқтайды.