Questo è un problema interattivo.

KUPC-kun ha scritto un programma che risolve il seguente problema.

Ti viene dato un albero $T = (V, E)$ con $N$ vertici. Per una sequenza $\{a_1, \dots, a_k\}$ di vertici di $T$ di lunghezza $k$, definisci il suo punteggio come segue. - Sia $d(u, v)$ il numero di archi sul cammino tra i vertici $u$ e $v$ in $T$. Allora il punteggio è $\prod_{i=1}^k d(a_i, a_{(i \bmod k)+1})$.

Viene dato un sottoinsieme $S$ di $V$. Per ogni $1 \le k \le N$, trova il seguente valore $q_k$. - La somma dei punteggi su tutte le sequenze di vertici $\{a_1, \dots, a_k\}$ di lunghezza $k$ i cui elementi appartengono a $S$, calcolata modulo $2^{61} - 1$.

KUPC-kun mantiene segrete in anticipo le informazioni sull'albero $T$ e continua a usare $T$ come albero fornito al programma.

Stai cercando di ricostruire le informazioni sulle foglie usando il programma sopra descritto. Indicando con $N$ il numero di vertici dell'albero, puoi porre la seguente domanda al massimo $N$ volte.

• Scegli un sottoinsieme $S$ di $V$ e chiedi l'output del programma.

Assumendo che il programma di KUPC-kun sia corretto, identifica tutte le foglie contenute nell'albero $T$ dalle informazioni ottenute tramite le domande.

Il giudice non è adattivo e l'albero $T$ è fissato prima che inizi l'interazione.

Protocollo di interazione

Per prima cosa, $N$ viene fornito dallo standard input. ($2 \le N \le 50$)

Per ogni domanda, stampa sullo standard output nel seguente formato.

? s1s2...sN

Qui, $s_1s_2\cdots s_N$ è una stringa di lunghezza $N$ che rappresenta il sottoinsieme $S$, dove $s_i = 1$ se $i \in S$, e $s_i = 0$ se $i \notin S$.

In risposta, viene fornito quanto segue dallo standard input.

q1 q2 ... qN

Una volta identificate tutte le foglie, stampa la tua risposta nel seguente formato.

! t1t2...tN

Qui, $t_1t_2\cdots t_N$ è una stringa di lunghezza $N$, dove $t_i = 1$ se $i$ è una foglia, e $t_i = 0$ se non è una foglia.

Dopo questo output, termina immediatamente il tuo programma.

Ogni volta che stampi qualcosa, aggiungi un ritorno a capo alla fine ed esegui il flush dello standard output.

Esempio

Input di esempio 1

5

0 8 0 32 0

0 44 108 968 3960

0 0 0 0 0

0 76 348 3336 22200

Output di esempio 1

? 00101

? 11001

? 10000

? 11111

! 11001

Note

Per il primo esempio, l'insieme degli archi dell'albero tenuto segreto dal giudice è $(1, 3), (2, 3), (3, 4), (4, 5)$.

Nella prima domanda, $S = \{3, 5\}$.

Nota che $d(3, 3) = 0, d(3, 5) = d(5, 3) = 2, d(5, 5) = 0$.

Ad esempio, ci sono le seguenti $4$ sequenze di vertici $a$ di lunghezza $2$ i cui elementi appartengono a $S$.

• Se $a = (3, 3)$, allora il punteggio di questa sequenza è $d(3, 3) \times d(3, 3) = 0 \times 0 = 0$.
• Se $a = (3, 5)$, allora il punteggio di questa sequenza è $d(3, 5) \times d(5, 3) = 2 \times 2 = 4$.
• Se $a = (5, 3)$, allora il punteggio di questa sequenza è $d(5, 3) \times d(3, 5) = 2 \times 2 = 4$.
• Se $a = (5, 5)$, allora il punteggio di questa sequenza è $d(5, 5) \times d(5, 5) = 0 \times 0 = 0$.

Il giudice risponde con $8$ per $q_2$, che è il resto della divisione di $0 + 4 + 4 + 0$ per $2^{61} - 1$.

Calcolando in modo analogo per le altre lunghezze delle sequenze, otteniamo la risposta del giudice 0 8 0 32 0.

Le foglie di questo albero sono i vertici $1, 2, 5$, e stampando ! 11001 si completa correttamente l'identificazione delle foglie.