To zadanie interaktywne. Limit wynosi $18\,000$ zapytań.

Jury ma tajny ciąg składający się z dokładnie 1000 cyfr binarnych. W każdym teście tego zadania ciąg jest ustalony z góry i się nie zmienia. Musisz znaleźć ten ciąg za pomocą zapytań.

W każdym zapytaniu wybierasz przedział $[a, b]$ ($1 \le a \le b \le 1000$), o który chcesz zapytać. Następnie jury rzuca monetą i podaje jedną z dwóch wartości, każdą z prawdopodobieństwem 50%:

1. Liczbę jedynek w przedziale $[a, b]$;
2. Wartość od $0$ do $b - a + 1$, która nie jest równa liczbie jedynek w tym przedziale, wybraną jednostajnie losowo.

Nie wolno użyć tego samego zapytania dwa razy. Wszystkie losowe wartości używane w zadaniu mają rozkład jednostajny i są niezależne.

Interakcja

Program uczestnika musi komunikować się z programem jury, wypisując polecenia w jednym z następujących formatów:

• ? a b. Zapytanie o przedział $[a, b]$. W odpowiedzi program jury wypisze jedną liczbę całkowitą: z prawdopodobieństwem 50% będzie to liczba jedynek w przedziale $[a, b]$, a w przeciwnym razie losowa wartość od $0$ do $b - a + 1$, inna niż ta liczba.
• ! ans. Odpowiedź do zadania, gdzie ans jest ciągiem długości 1000 złożonym z zer i jedynek. Po tym poleceniu program uczestnika powinien natychmiast zakończyć działanie.

Przykład

Wejście 1

2
3
3
1
3

Wyjście 1

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

Uwagi

Powyższy przykład służy jedynie do zademonstrowania formatu. W tym przykładzie ciąg ma długość 5. W rzeczywistym pierwszym teście, tak jak we wszystkich pozostałych testach, długość zgadywanego ciągu wynosi dokładnie 1000.