Se le da un árbol $T = (V, E)$ con $N$ vértices. Para una secuencia $\{a_1, \dots, a_k\}$ de vértices de $T$ de longitud $k$, defina su puntuación de la siguiente manera:

• Sea $d(u, v)$ el número de aristas en el camino entre los vértices $u$ y $v$ en $T$. Entonces, la puntuación es $\prod_{i=1}^{k} d(a_i, a_{(i \bmod k)+1})$.

Se proporciona un subconjunto $S$ de $V$. Para cada $1 \le k \le N$, encuentre el siguiente valor $q_k$:

• La suma de las puntuaciones sobre todas las secuencias de vértices $\{a_1, \dots, a_k\}$ de longitud $k$ cuyos elementos pertenecen a $S$, tomada módulo $2^{61} - 1$.

KUPC-kun mantiene en secreto la información del árbol $T$ de antemano y continúa usando $T$ como el árbol dado al programa. Usted intenta recuperar la información de las hojas usando el programa anterior. Siendo $N$ el número de vértices del árbol, usted puede realizar la siguiente pregunta como máximo $N$ veces:

• Elija un subconjunto $S$ de $V$ y solicite la salida del programa.

Asumiendo que el programa de KUPC-kun es correcto, identifique todas las hojas contenidas en el árbol $T$ a partir de la información obtenida a través de las preguntas. El juez no es adaptativo y el árbol $T$ está fijo antes de que comience la interacción.

Protocolo de interacción

Primero, se proporciona $N$ desde la entrada estándar. ($2 \le N \le 50$)

Para cada pregunta, imprima en la salida estándar el siguiente formato:

? s1s2 · · · sN

Aquí, $s_1s_2 \dots s_N$ es una cadena de longitud $N$ que representa el subconjunto $S$, donde $s_i = 1$ si $i \in S$, y $s_i = 0$ si $i \notin S$.

En respuesta, se proporciona lo siguiente desde la entrada estándar:

q1 q2 · · · qN

Una vez que haya identificado todas las hojas, imprima su respuesta en el siguiente formato:

! t1t2 · · · tN

Aquí, $t_1t_2 \dots t_N$ es una cadena de longitud $N$, donde $t_i = 1$ si $i$ es una hoja, y $t_i = 0$ si no es una hoja.

Después de esta salida, termine su programa inmediatamente.

Siempre que imprima algo, añada un salto de línea al final y vacíe el búfer de la salida estándar.

Ejemplos

Entrada 1

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

Salida 1

? 00101
? 11001
? 10000
? 11111
! 11001

Nota

Para el primer ejemplo, el conjunto de aristas del árbol mantenido en secreto por el juez es $(1, 3), (2, 3), (3, 4), (4, 5)$. En la primera pregunta, $S = \{3, 5\}$. Note que $d(3, 3) = 0$, $d(3, 5) = d(5, 3) = 2$, $d(5, 5) = 0$. Por ejemplo, existen las siguientes 4 secuencias de vértices $a$ de longitud 2 cuyos elementos pertenecen a $S$:

• Si $a = (3, 3)$, entonces la puntuación de esta secuencia es $d(3, 3) \times d(3, 3) = 0 \times 0 = 0$
• Si $a = (3, 5)$, entonces la puntuación de esta secuencia es $d(3, 5) \times d(5, 3) = 2 \times 2 = 4$
• Si $a = (5, 3)$, entonces la puntuación de esta secuencia es $d(5, 3) \times d(3, 5) = 2 \times 2 = 4$
• Si $a = (5, 5)$, entonces la puntuación de esta secuencia es $d(5, 5) \times d(5, 5) = 0 \times 0 = 0$

El juez responde con 8 para $q_2$, que es el resto cuando $0 + 4 + 4 + 0$ se divide por $2^{61} - 1$. Calculando de manera similar para las otras longitudes de secuencia, obtenemos la respuesta del juez $0\ 8\ 0\ 32\ 0$. Las hojas de este árbol son los vértices $1, 2, 5$, y la salida ! 11001 completa correctamente la identificación de las hojas.