Це інтерактивна задача. Обмеження на кількість запитів — $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.