Dies ist ein interaktives Problem.

Little Cyan Fish hat einen versteckten einfachen ungerichteten Graphen mit $n$ Knoten, die von $1$ bis $n$ nummeriert sind. Du kennst den Wert von $n$, aber du kennst keine der Kanten. Little Cyan Fish liebt das Konzept eines Schnitts (cut). Für eine Knotenmenge $S$ bezeichne $\operatorname{cut}(S)$ die Anzahl der Kanten, die genau einen Endpunkt in $S$ haben.

Little Cyan Fish erlaubt dir, Schnitte durch Anfragen zu vergleichen. In einer Anfrage wählst du zwei Knotenmengen $S_1$ und $S_2$. Little Cyan Fish teilt dir mit, ob $\operatorname{cut}(S_1)$ kleiner als, gleich oder größer als $\operatorname{cut}(S_2)$ ist.

Du kannst wahrscheinlich schon ahnen, dass es als Nächstes um die Rekonstruktion des Graphen geht, aber dieses Mal ist die Aufgabe einfacher. Little Cyan Fish gibt dir einen Knoten $u$, und er möchte, dass du in höchstens $n + 10$ Anfragen alle zu $u$ benachbarten Knoten findest.

Eingabe

Die erste Zeile der Eingabe enthält zwei ganze Zahlen $n$ und $u$ ($1 \le n \le 1000$, $1 \le u \le n$), die die Anzahl der Knoten bzw. den gegebenen Knoten angeben. Danach beginnt die Interaktion.

Interaktion

Um eine Anfrage zu stellen, gib eine Zeile im folgenden Format aus:

$$?\ s_1\ s_2$$

wobei $s_1$ und $s_2$ Zeichenketten der Länge $n$ sind, die nur aus den Zeichen 0 und 1 bestehen. Für jedes $j \in \{1, 2\}$ gehört der Knoten $i$ genau dann zu $S_j$, wenn das $i$-te Zeichen von $s_j$ gleich 1 ist. Die Mengen dürfen leer sein, sich überschneiden und gleich sein.

Als Antwort auf die Anfrage erhältst du ein einzelnes Zeichen <, = oder >, was bedeutet, dass $\operatorname{cut}(S_1)$ kleiner als, gleich bzw. größer als $\operatorname{cut}(S_2)$ ist. Du musst sicherstellen, dass die Anzahl der von dir gestellten Anfragen $n + 10$ nicht überschreitet.

Um die Antwort zu melden, gib eine Zeile im folgenden Format aus:

$$!\ k\ v_1\ v_2\ \dots\ v_k$$

wobei $k$ ($0 \le k \le n - 1$) die Anzahl der zu $u$ benachbarten Knoten ist und $v_1, v_2, \ldots, v_k$ ihre paarweise verschiedenen Nummern in beliebiger Reihenfolge sind. Falls $k = 0$ gilt, gib ! 0 aus. Das Melden der Antwort zählt nicht als Anfrage. Dein Programm muss sich unmittelbar nach dem Melden der Antwort beenden.

Vergiss nicht, nach der Ausgabe einer Anfrage oder dem Melden der Antwort einen Zeilenumbruch auszugeben und den Ausgabepuffer zu leeren (flush). Wenn du eine ungültige Anfrage stellst oder das Anfragelimit überschreitest, schließt der Interaktor den Eingabestrom und dein Programm muss sich beenden.

In diesem Problem ist der Interaktor adaptiv. Das bedeutet, dass sich der Graph abhängig von deinen Anfragen ändern kann, solange er keiner bisherigen Antwort widerspricht. Deine Antwort muss für jeden Graphen korrekt sein, der mit allen erhaltenen Antworten konsistent ist.

Beispiele

Eingabe 1

4 1

<

=

<

=

Ausgabe 1

? 0000 1000

? 0100 1100

? 0010 1010

? 0001 1001

! 2 2 4

Hinweis

Ein Graph, der mit der Beispielinteraktion konsistent ist, besitzt die Kanten $(1, 2)$, $(1, 4)$ und $(2, 3)$.

Testwerkzeug: Es wird ein Testwerkzeug bereitgestellt, um den Teilnehmern bei der Entwicklung und dem Testen ihrer Lösungen zu helfen. Du kannst dieses Werkzeug aus den Anhängen herunterladen. Führe das Werkzeug mit der Option -h aus, um Benutzungshinweise anzuzeigen. Das Werkzeug überprüft die Interaktion und die gemeldete Antwort, setzt jedoch weder das Zeit- noch das Speicherlimit durch.

Das Testwerkzeug verwendet während der gesamten Interaktion einen festen Graphen, der in seiner Eingabedatei angegeben ist, während der offizielle Interaktor adaptiv ist. Das Bestehen von Tests mit dem Testwerkzeug garantiert nicht, dass deine Lösung gegenüber dem offiziellen Interaktor korrekt ist.