Þetta er gagnvirkt verkefni.

KUPC-kun skrifaði forrit sem leysir eftirfarandi verkefni.

Gefin er tré $T = (V, E)$ með $N$ hnútum. Fyrir runu $\{a_1, \dots, a_k\}$ af hnútum í $T$ af lengd $k$ skilgreinum við stig hennar sem hér segir. - Látum $d(u, v)$ vera fjölda leggja á veginum milli hnúta $u$ og $v$ í $T$. Þá eru stigin $\prod_{i=1}^k d(a_i, a_{(i \bmod k)+1})$.

Gefin er hlutmengi $S$ af $V$. Fyrir hvert $1 \le k \le N$, finndu eftirfarandi gildi $q_k$. - Summa stiganna yfir allar hnútarunur $\{a_1, \dots, a_k\}$ af lengd $k$ þar sem stök þeirra tilheyra $S$, tekin modulo $2^{61} - 1$.

KUPC-kun heldur upplýsingunum um tréð $T$ leyndum fyrirfram og heldur áfram að nota $T$ sem tréð sem gefið er forritinu.

Þú ert að reyna að endurheimta upplýsingar um laufin með því að nota forritið hér að ofan. Ef fjöldi hnúta í trénu er $N$ máttu spyrja eftirfarandi spurningar í mesta lagi $N$ sinnum.

• Veldu hlutmengi $S$ af $V$ og biddu um úttak forritsins.

Að því gefnu að forrit KUPC-kun sé rétt, finndu öll lauf sem eru í trénu $T$ út frá upplýsingunum sem fást með spurningunum.

Dómarinn er ekki aðlögunarhæfur (not adaptive) og tréð $T$ er ákveðið áður en samskiptin hefjast.

Samskiptareglur

Fyrst er $N$ gefið úr staðalinntaki. ($2 \le N \le 50$)

Fyrir hverja spurningu skal skrifa út í staðalúttak á eftirfarandi sniði.

? s1s2...sN

Hér er $s_1s_2\cdots s_N$ strengur af lengd $N$ sem táknar hlutmengið $S$, þar sem $s_i = 1$ ef $i \in S$, og $s_i = 0$ ef $i \notin S$.

Sem svar er eftirfarandi gefið úr staðalinntaki.

q1 q2 ... qN

Þegar þú hefur fundið öll laufin skaltu skrifa út svarið þitt á eftirfarandi sniði.

! t1t2...tN

Hér er $t_1t_2\cdots t_N$ strengur af lengd $N$, þar sem $t_i = 1$ ef $i$ er lauf, og $t_i = 0$ ef það er ekki lauf.

Eftir þetta úttak skaltu stöðva keyrslu forritsins þíns samstundis.

Í hvert sinn sem þú skrifar eitthvað út skaltu bæta við nýrri línu í lokin og tæma (flush) staðalúttakið.

Dæmi

Dæmi um inntak 1

5

0 8 0 32 0

0 44 108 968 3960

0 0 0 0 0

0 76 348 3336 22200

Dæmi um úttak 1

? 00101

? 11001

? 10000

? 11111

! 11001

Athugasemd

Í fyrra dæminu er leggjamengi trésins sem dómarinn heldur leyndu $(1, 3), (2, 3), (3, 4), (4, 5)$.

Í fyrstu spurningunni er $S = \{3, 5\}$.

Athugið að $d(3, 3) = 0, d(3, 5) = d(5, 3) = 2, d(5, 5) = 0$.

Til dæmis eru til eftirfarandi $4$ hnútarunur $a$ af lengd $2$ þar sem stökin tilheyra $S$.

• Ef $a = (3, 3)$, þá eru stig þessarar runu $d(3, 3) \times d(3, 3) = 0 \times 0 = 0$.
• Ef $a = (3, 5)$, þá eru stig þessarar runu $d(3, 5) \times d(5, 3) = 2 \times 2 = 4$.
• Ef $a = (5, 3)$, þá eru stig þessarar runu $d(5, 3) \times d(3, 5) = 2 \times 2 = 4$.
• Ef $a = (5, 5)$, þá eru stig þessarar runu $d(5, 5) \times d(5, 5) = 0 \times 0 = 0$.

Dómarinn svarar með $8$ fyrir $q_2$, sem er afgangurinn þegar $0 + 4 + 4 + 0$ er deilt með $2^{61} - 1$.

Með því að reikna á svipaðan hátt fyrir hinar lengdirnar á rununum fáum við svar dómarans 0 8 0 32 0.

Laufin á þessu tré eru hnútar $1, 2, 5$, og að skrifa út ! 11001 lýkur greiningu laufanna rétt.