Dies ist eine interaktive Aufgabe. Es sind höchstens $18\,000$ Anfragen erlaubt.

Die Jury besitzt eine geheime Zeichenkette aus genau 1000 Binärziffern. In jedem Test dieser Aufgabe wird die Zeichenkette im Voraus festgelegt und ändert sich nicht. Du musst diese Zeichenkette mithilfe von Anfragen finden.

Bei jeder Anfrage wählst du ein Intervall $[a, b]$ ($1 \le a \le b \le 1000$), nach dem du fragen möchtest. Danach wirft die Jury eine Münze und gibt dir einen der folgenden beiden Werte, jeweils mit einer Wahrscheinlichkeit von 50%:

1. Die Anzahl der Einsen im Intervall $[a, b]$;
2. Einen gleichverteilt zufällig gewählten Wert von $0$ bis $b - a + 1$, der nicht gleich der Anzahl der Einsen in diesem Intervall ist.

Du darfst dieselbe Anfrage nicht zweimal verwenden. Alle in dieser Aufgabe verwendeten Zufallswerte sind gleichverteilt und unabhängig.

Interaktion

Das Teilnehmerprogramm muss mit dem Juryprogramm interagieren, indem es Befehle in einem der folgenden Formate ausgibt:

• ? a b. Eine Anfrage zum Intervall $[a, b]$. Zur Beantwortung gibt das Juryprogramm eine einzelne ganze Zahl aus: Mit einer Wahrscheinlichkeit von 50% ist dies die Anzahl der Einsen im Intervall $[a, b]$, andernfalls ein davon verschiedener Zufallswert von $0$ bis $b - a + 1$.
• ! ans. Die Antwort auf die Aufgabe, wobei ans eine Zeichenkette der Länge 1000 aus Nullen und Einsen ist. Nach diesem Befehl soll das Teilnehmerprogramm sofort enden.

Beispiele

Eingabe 1

2
3
3
1
3

Ausgabe 1

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

Hinweis

Das obige Beispiel dient nur zur Veranschaulichung des Formats. In diesem Beispiel hat die Zeichenkette die Länge 5. Im tatsächlichen ersten Test sowie in allen weiteren Tests ist die Länge der zu erratenden Zeichenkette genau 1000.