Esta tarea es interactiva.

Existe una cadena binaria* oculta ~s~ de longitud ~n~. Tu objetivo es descubrir cuál es esta cadena.

Para hacerlo, puedes realizar un máximo de ~1432~ consultas. En cada consulta, debes imprimir ? q, donde ~q~ es una cadena binaria de longitud ~n~. Se responderá con:

• 2: si ~q~ es exactamente igual a ~s~, es decir, si ~|\{i: s_i = q_i\}| = n~;
• 1: si ~q~ coincide con ~s~ en exactamente ~\frac{n}{2}~ posiciones, es decir, si ~|\{i: s_i = q_i\}| = \frac{n}{2}~;
• 0: en cualquier otro caso.

Cuando hayas encontrado la respuesta, imprime ! x, donde ~x~ debe ser la cadena oculta ~s~, y termina tu programa inmediatamente.

* Una cadena binaria es una cadena formada únicamente por los caracteres 0 y 1. Por ejemplo, 010100, 11010 y 00000 son cadenas binarias, mientras que 0123, a01010b y b010 no lo son.

Interacción

La primera línea de la entrada contiene un entero ~n~ (~2 \le n \le 1000~). Se garantiza que ~n~ es par. Luego de esto, podrás realizar las consultas o dar una respuesta final.

• ? q ~-~ realizar una consulta con una cadena binaria ~q~ de longitud ~n~. El resultado será un entero ~r \in \{0, 1, 2\}~ de acuerdo con lo que se describió anteriormente.
• ! x ~-~ responder con una cadena binaria ~x~ de longitud ~n~.

Para esta tarea, el interactor no es adaptativo. Esto significa que la cadena ~s~ no cambiará durante la interacción.

Después de imprimir cada acción del programa, incluye un salto de línea y vacía el flujo de salida. Si usas cout << ... << endl en C++, el flujo de salida se vacía automáticamente, por lo que no necesitas hacer nada más. Si usas otro método de salida, se recomienda vaciar el flujo de salida con fflush(stdout) o cout.flush(). Ten en cuenta que el salto de línea debe aparecer siempre.

Subtareas

Esta tarea está compuesta por ~6~ subtareas.

Los puntos de una subtarea se otorgan solo si se aceptan todos los casos de esa subtarea.

Subtarea	Puntos	Restricciones adicionales	Dependencias
~1~	~8~	La cadena oculta está ordenada en orden creciente.	~-~
~2~	~15~	~2 \le n \le 10~.	~-~
~3~	~23~	La cadena oculta tiene la misma cantidad de 0 y 1.	~-~
~4~	~14~	~2 \le n \le 35~.	~2~
~5~	~23~	~2 \le n \le 700~.	~2,4~
~6~	~17~	Sin restricciones adicionales.	~1,2,3,4,5~

Ejemplos

Entrada 1

2

1

0

2

Salida 1

? 01

? 11

? 00

! 00

Entrada 2

4

1

1

1

2

Salida 2

? 0000

? 1111

? 0011

? 0101

! 0101