Vous disposez d'un arbre $T = (V, E)$ avec $N$ sommets. Pour une séquence $\{a_1, \dots, a_k\}$ de sommets de $T$ de longueur $k$, définissez son score comme suit :

• Soit $d(u, v)$ le nombre d'arêtes sur le chemin entre les sommets $u$ et $v$ dans $T$. Le score est alors $\prod_{i=1}^{k} d(a_i, a_{(i \mod k)+1})$.

Un sous-ensemble $S$ de $V$ est donné. Pour chaque $1 \le k \le N$, trouvez la valeur $q_k$ suivante :

• La somme des scores sur toutes les séquences de sommets $\{a_1, \dots, a_k\}$ de longueur $k$ dont les éléments appartiennent à $S$, prise modulo $2^{61} - 1$.

KUPC-kun conserve secrètement les informations de l'arbre $T$ à l'avance et continue d'utiliser $T$ comme l'arbre fourni au programme. Vous essayez de récupérer les informations sur les feuilles en utilisant le programme ci-dessus. En notant $N$ le nombre de sommets de l'arbre, vous pouvez poser la question suivante au plus $N$ fois :

• Choisir un sous-ensemble $S$ de $V$ et demander la sortie du programme.

En supposant que le programme de KUPC-kun est correct, identifiez toutes les feuilles contenues dans l'arbre $T$ à partir des informations obtenues par les questions. Le juge n'est pas adaptatif, et l'arbre $T$ est fixé avant le début de l'interaction.

Interaction

Tout d'abord, $N$ est donné via l'entrée standard. ($2 \le N \le 50$)

Pour chaque question, affichez sur la sortie standard le format suivant :

? $s_1s_2 \dots s_N$

Ici, $s_1s_2 \dots s_N$ est une chaîne de longueur $N$ représentant le sous-ensemble $S$, où $s_i = 1$ si $i \in S$, et $s_i = 0$ si $i \notin S$.

En réponse, ce qui suit est donné via l'entrée standard :

$q_1 \ q_2 \ \dots \ q_N$

Une fois que vous avez identifié toutes les feuilles, affichez votre réponse dans le format suivant :

! $t_1t_2 \dots t_N$

Ici, $t_1t_2 \dots t_N$ est une chaîne de longueur $N$, où $t_i = 1$ si $i$ est une feuille, et $t_i = 0$ si ce n'est pas une feuille.

Après cette sortie, terminez immédiatement votre programme. Chaque fois que vous affichez quelque chose, ajoutez un saut de ligne à la fin et videz le tampon de la sortie standard.

Exemples

Entrée 1

5
0 8 0 32 0
0 44 108 968 3960
0 0 0 0 0
0 76 348 3336 22200

Sortie 1

? 00101
? 11001
? 10000
? 11111
! 11001

Remarque

Pour le premier exemple, l'ensemble des arêtes de l'arbre secrètement détenu par le juge est $(1, 3), (2, 3), (3, 4), (4, 5)$. Dans la première question, $S = \{3, 5\}$. Notez que $d(3, 3) = 0$, $d(3, 5) = d(5, 3) = 2$, $d(5, 5) = 0$. Pour exemple, il existe les 4 séquences de sommets $a$ de longueur 2 dont les éléments appartiennent à $S$ :

• Si $a = (3, 3)$, alors le score de cette séquence est $d(3, 3) \times d(3, 3) = 0 \times 0 = 0$
• Si $a = (3, 5)$, alors le score de cette séquence est $d(3, 5) \times d(5, 3) = 2 \times 2 = 4$
• Si $a = (5, 3)$, alors le score de cette séquence est $d(5, 3) \times d(3, 5) = 2 \times 2 = 4$
• Si $a = (5, 5)$, alors le score de cette séquence est $d(5, 5) \times d(5, 5) = 0 \times 0 = 0$

Le juge répond 8 pour $q_2$, qui est le reste de la division de $0 + 4 + 4 + 0$ par $2^{61} - 1$. En calculant de la même manière pour les autres longueurs de séquence, nous obtenons la réponse du juge $0 \ 8 \ 0 \ 32 \ 0$. Les feuilles de cet arbre sont les sommets 1, 2, 5, et l'affichage de ! 11001 complète correctement l'identification des feuilles.