Dette er en interaktiv oppgave.

KUPC-kun skrev et program som løser følgende oppgave.

Du får et tre $T = (V, E)$ med $N$ noder. For en følge $\{a_1, \dots, a_k\}$ av noder i $T$ med lengde $k$, defineres poengsummen dens som følger. - La $d(u, v)$ være antallet kanter på stien mellom nodene $u$ og $v$ i $T$. Da er poengsummen $\prod_{i=1}^k d(a_i, a_{(i \bmod k)+1})$.

En delmengde $S$ av $V$ er gitt. For hver $1 \le k \le N$, finn følgende verdi $q_k$. - Summen av poengsummene over alle nodefølger $\{a_1, \dots, a_k\}$ med lengde $k$ der elementene tilhører $S$, tatt modulo $2^{61} - 1$.

KUPC-kun holder informasjonen om treet $T$ hemmelig på forhånd, og fortsetter å bruke $T$ som treet som gis til programmet.

Du prøver å gjenopprette informasjonen om løvnodene ved hjelp av programmet ovenfor. Hvis antallet noder i treet er $N$, kan du stille følgende spørsmål høyst $N$ ganger.

• Velg en delmengde $S$ av $V$ og spør etter utdataene fra programmet.

Forutsatt at programmet til KUPC-kun er riktig, identifiser alle løvnoder i treet $T$ ut fra informasjonen du får gjennom spørsmålene.

Dommeren er ikke adaptiv, og treet $T$ er fastsatt før interaksjonen starter.

Interaksjonsprotokoll

Først gis $N$ fra standard inndata. ($2 \le N \le 50$)

For hvert spørsmål skal du skrive ut til standard utdata i følgende format.

? s1s2...sN

Her er $s_1s_2\cdots s_N$ en streng med lengde $N$ som representerer delmengden $S$, der $s_i = 1$ hvis $i \in S$, og $s_i = 0$ hvis $i \notin S$.

Som svar gis følgende fra standard inndata.

q1 q2 ... qN

Når du har identifisert alle løvnodene, skriver du ut svaret ditt i følgende format.

! t1t2...tN

Her er $t_1t_2\cdots t_N$ en streng med lengde $N$, der $t_i = 1$ hvis $i$ er en løvnode, og $t_i = 0$ hvis den ikke er en løvnode.

Etter denne utskriften må du avslutte programmet ditt umiddelbart.

Hver gang du skriver ut noe, må du legge til et linjeskift på slutten og tømme (flush) standard utdata.

Eksempel

Eksempelinndata 1

5

0 8 0 32 0

0 44 108 968 3960

0 0 0 0 0

0 76 348 3336 22200

Eksempelutdata 1

? 00101

? 11001

? 10000

? 11111

! 11001

Forklaring

For det første eksempelet er kantmengden til treet som dommeren holder hemmelig $(1, 3), (2, 3), (3, 4), (4, 5)$.

I det første spørsmålet er $S = \{3, 5\}$.

Merk at $d(3, 3) = 0, d(3, 5) = d(5, 3) = 2, d(5, 5) = 0$.

For eksempel finnes det følgende $4$ nodefølger $a$ med lengde $2$ der elementene tilhører $S$.

• Hvis $a = (3, 3)$, er poengsummen til denne følgen $d(3, 3) \times d(3, 3) = 0 \times 0 = 0$.
• Hvis $a = (3, 5)$, er poengsummen til denne følgen $d(3, 5) \times d(5, 3) = 2 \times 2 = 4$.
• Hvis $a = (5, 3)$, er poengsummen til denne følgen $d(5, 3) \times d(3, 5) = 2 \times 2 = 4$.
• Hvis $a = (5, 5)$, er poengsummen til denne følgen $d(5, 5) \times d(5, 5) = 0 \times 0 = 0$.

Dommeren svarer med $8$ for $q_2$, som er resten når $0 + 4 + 4 + 0$ divideres med $2^{61} - 1$.

Ved å regne tilsvarende for de andre følgelengdene får vi dommerens svar 0 8 0 32 0.

Løvnodene i dette treet er nodene $1, 2, 5$, og å skrive ut ! 11001 fullfører identifiseringen av løvnodene korrekt.