Dies ist ein interaktives Problem.

KUPC-kun hat ein Programm geschrieben, das das folgende Problem löst.

Gegeben ist ein Baum $T = (V, E)$ mit $N$ Knoten. Für eine Folge $\{a_1, \dots, a_k\}$ von Knoten aus $T$ der Länge $k$ wird ihr Score wie folgt definiert. - Sei $d(u, v)$ die Anzahl der Kanten auf dem Pfad zwischen den Knoten $u$ und $v$ in $T$. Dann ist der Score $\prod_{i=1}^k d(a_i, a_{(i \bmod k)+1})$.

Eine Teilmenge $S$ von $V$ ist gegeben. Bestimme für jedes $1 \le k \le N$ den folgenden Wert $q_k$. - Die Summe der Scores über alle Knotenfolgen $\{a_1, \dots, a_k\}$ der Länge $k$, deren Elemente zu $S$ gehören, modulo $2^{61} - 1$.

KUPC-kun hält die Informationen über den Baum $T$ im Voraus geheim und verwendet $T$ durchgehend als den an das Programm übergebenen Baum.

Du versuchst, mithilfe des obigen Programms die Informationen über die Blätter zu rekonstruieren. Wenn die Anzahl der Knoten des Baums $N$ beträgt, darfst du höchstens $N$-mal die folgende Frage stellen.

• Wähle eine Teilmenge $S$ von $V$ und frage nach der Ausgabe des Programms.

Unter der Annahme, dass KUPC-kuns Programm korrekt ist, identifiziere anhand der durch die Fragen gewonnenen Informationen alle im Baum $T$ enthaltenen Blätter.

Der Judge ist nicht adaptiv, und der Baum $T$ steht vor Beginn der Interaktion fest.

Interaktionsprotokoll

Zuerst wird $N$ über die Standardeingabe eingelesen. ($2 \le N \le 50$)

Gib für jede Frage im folgenden Format auf der Standardausgabe aus.

? s1s2...sN

Hierbei ist $s_1s_2\cdots s_N$ eine Zeichenkette der Länge $N$, die die Teilmenge $S$ darstellt, wobei $s_i = 1$ gilt, falls $i \in S$, und $s_i = 0$, falls $i \notin S$.

Als Antwort wird Folgendes über die Standardeingabe gegeben.

q1 q2 ... qN

Sobald du alle Blätter identifiziert hast, gib deine Antwort im folgenden Format aus.

! t1t2...tN

Hierbei ist $t_1t_2\cdots t_N$ eine Zeichenkette der Länge $N$, wobei $t_i = 1$ gilt, falls $i$ ein Blatt ist, und $t_i = 0$, falls es kein Blatt ist.

Beende dein Programm unmittelbar nach dieser Ausgabe.

Füge bei jeder Ausgabe am Ende einen Zeilenumbruch an und leere den Ausgabepuffer (flush).

Beispiel

Beispieleingabe 1

5

0 8 0 32 0

0 44 108 968 3960

0 0 0 0 0

0 76 348 3336 22200

Beispielausgabe 1

? 00101

? 11001

? 10000

? 11111

! 11001

Hinweis

Für das erste Beispiel lautet die vom Judge geheim gehaltene Kantenmenge des Baums $(1, 3), (2, 3), (3, 4), (4, 5)$.

In der ersten Frage ist $S = \{3, 5\}$.

Beachte, dass $d(3, 3) = 0, d(3, 5) = d(5, 3) = 2, d(5, 5) = 0$ gilt.

Beispielsweise gibt es die folgenden $4$ Knotenfolgen $a$ der Länge $2$, deren Elemente zu $S$ gehören.

• Falls $a = (3, 3)$, beträgt der Score dieser Folge $d(3, 3) \times d(3, 3) = 0 \times 0 = 0$.
• Falls $a = (3, 5)$, beträgt der Score dieser Folge $d(3, 5) \times d(5, 3) = 2 \times 2 = 4$.
• Falls $a = (5, 3)$, beträgt der Score dieser Folge $d(5, 3) \times d(3, 5) = 2 \times 2 = 4$.
• Falls $a = (5, 5)$, beträgt der Score dieser Folge $d(5, 5) \times d(5, 5) = 0 \times 0 = 0$.

Der Judge antwortet mit $8$ für $q_2$, was dem Rest bei der Division von $0 + 4 + 4 + 0$ durch $2^{61} - 1$ entspricht.

Durch analoge Berechnung für die anderen Folgenlängen erhalten wir die Antwort 0 8 0 32 0 des Judges.

Die Blätter dieses Baums sind die Knoten $1, 2, 5$, und die Ausgabe von ! 11001 schließt die Identifizierung der Blätter korrekt ab.