Este es un problema interactivo. El límite es de $18\,000$ consultas.

El jurado tiene una cadena secreta que consta de exactamente 1000 dígitos binarios. En cada prueba de este problema, la cadena se fija de antemano y no cambia. Debes encontrar esta cadena mediante consultas.

En cada consulta, eliges un segmento $[a, b]$ ($1 \le a \le b \le 1000$) sobre el que preguntar. Después, el jurado lanza una moneda y te da uno de los dos valores siguientes, cada uno con una probabilidad del 50%:

1. El número de unos en el segmento $[a, b]$;
2. Un valor entre $0$ y $b - a + 1$ que no sea igual al número de unos en este segmento, elegido de manera uniforme al azar.

No se permite utilizar la misma consulta dos veces. Todos los valores aleatorios usados en este problema son uniformes e independientes.

Interacción

El programa del participante debe interactuar con el programa del jurado imprimiendo órdenes en uno de los siguientes formatos:

• ? a b. Una consulta para el segmento $[a, b]$. Para responder, el programa del jurado imprimirá un único entero que, con probabilidad del 50%, será el número de unos en el segmento $[a, b]$, y en caso contrario será un valor aleatorio entre $0$ y $b - a + 1$ distinto de ese número.
• ! ans. La respuesta al problema, donde ans es una cadena de longitud 1000 compuesta por ceros y unos. Después de esta orden, el programa del participante debe terminar inmediatamente.

Ejemplos

Entrada 1

2
3
3
1
3

Salida 1

? 1 3
? 1 5
? 3 5
? 2 3
? 2 5
! 01101

Nota

El ejemplo anterior solo se proporciona para demostrar el formato. En este ejemplo, la cadena tiene longitud 5. En la primera prueba real, así como en todas las demás pruebas, la longitud de la cadena que se debe adivinar es exactamente 1000.