Este é um problema interativo. O limite é de $18\,000$ consultas.

O júri tem uma cadeia secreta que consiste em exatamente 1000 dígitos binários. Em cada teste deste problema, a cadeia é fixada antecipadamente e não muda. Você deve encontrar essa cadeia usando consultas.

Em cada consulta, você escolhe um segmento $[a, b]$ ($1 \le a \le b \le 1000$) sobre o qual perguntar. Em seguida, o júri lança uma moeda e fornece um dos dois valores seguintes, cada um com probabilidade de 50%:

1. O número de uns no segmento $[a, b]$;
2. Um valor entre $0$ e $b - a + 1$ que não seja igual ao número de uns nesse segmento, escolhido uniformemente ao acaso.

Você não pode usar a mesma consulta duas vezes. Todos os valores aleatórios usados neste problema são uniformes e independentes.

Interação

O programa do participante deve interagir com o programa do júri imprimindo comandos em um dos seguintes formatos:

• ? a b. Uma consulta sobre o segmento $[a, b]$. Para responder, o programa do júri imprimirá um único inteiro que, com probabilidade de 50%, será o número de uns no segmento $[a, b]$, e caso contrário será um valor aleatório entre $0$ e $b - a + 1$ diferente desse número.
• ! ans. A resposta ao problema, em que ans é uma cadeia de comprimento 1000 composta por zeros e uns. Após esse comando, o programa do participante deve terminar imediatamente.

Exemplos

Entrada 1

2
3
3
1
3

Saída 1

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

Nota

O exemplo acima serve apenas para demonstrar o formato. Nesse exemplo, a cadeia tem comprimento 5. No primeiro teste real, assim como em todos os outros testes, o comprimento da cadeia a adivinhar é exatamente 1000.