Это интерактивная задача. Ограничение на число запросов — $18\,000$.

У жюри есть секретная строка, состоящая ровно из 1000 двоичных цифр. В каждом тесте этой задачи строка зафиксирована заранее и не меняется. Вам нужно найти эту строку с помощью запросов.

В каждом запросе вы выбираете отрезок $[a, b]$ ($1 \le a \le b \le 1000$), о котором хотите спросить. Затем жюри подбрасывает монету и сообщает одно из двух значений, каждое с вероятностью 50%:

1. Число единиц на отрезке $[a, b]$;
2. Равномерно случайно выбранное значение от $0$ до $b - a + 1$, не равное числу единиц на этом отрезке.

Вам нельзя использовать один и тот же запрос дважды. Все случайные значения в этой задаче равномерно распределены и независимы.

Протокол взаимодействия

Программа участника должна взаимодействовать с программой жюри, выводя команды в одном из следующих форматов:

• ? a b. Запрос для отрезка $[a, b]$. В ответ программа жюри выведет одно целое число: с вероятностью 50% это будет число единиц на отрезке $[a, b]$, а иначе — случайное значение от $0$ до $b - a + 1$, не равное ему.
• ! ans. Ответ на задачу, где ans — строка длины 1000 из нулей и единиц. После этой команды программа участника должна немедленно завершиться.

Примеры

Входные данные 1

2
3
3
1
3

Выходные данные 1

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

Примечание

Пример выше приведён только для демонстрации формата. В этом примере длина строки равна 5. В настоящем первом тесте, как и во всех остальных тестах, длина угадываемой строки равна ровно 1000.