Dies ist eine interaktive Aufgabe. Denke daran, nach jeder Ausgabe den Ausgabepuffer zu leeren. Dazu kannst du Folgendes verwenden:

• fflush(stdout) oder cout.flush() in C/C++;
• System.out.flush() in Java und Kotlin;
• sys.stdout.flush() in Python;
• Für andere Sprachen siehe deren Dokumentation.

Little Cyan Fish hat eine geheime Permutation $p_0,p_1,\ldots,p_n$ der Länge $n+1$, die aus den ganzen Zahlen von $0$ bis $n$ besteht. Er möchte, dass du diese geheime Permutation errätst. Dafür erlaubt dir Little Cyan Fish höchstens $1024$ Anfragen der folgenden Form:

• ? i j: Erhalte den Index $k$ ($0\le k\le n$), für den $p_k=|p_i-p_j|$ gilt.

Für eine gültige Anfrage musst du natürlich sicherstellen, dass $i$ und $j$ zwei ganze Zahlen in $[0,n]$ sind. Wenn beispielsweise $p_0=2,p_1=0,p_2=1$ gilt, liefert die Anfrage ? 0 2 den Index $2$, denn $|p_0-p_2|=|2-1|=1=p_2$.

Little Cyan Fish möchte, dass du eine Strategie zum Finden der Permutation entwickelst. Natürlich möchte er nicht, dass du das Spiel zu leicht gewinnst. Daher wird er die Permutation $p$ adaptiv ändern, um dir eine Falle zu stellen (Einzelheiten findest du unter „Interaktion“).

Eingabe

Es gibt mehrere Testfälle. Die erste Eingabezeile enthält eine einzelne ganze Zahl $T$ ($1\le T\le100$), die Anzahl der Testfälle.

Für jeden Testfall enthält die erste Eingabezeile eine einzelne ganze Zahl $n$ ($1\le n\le1000$). Danach beginnt die Interaktion.

Interaktion

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

$$?\ i\ j$$

Dabei sind $i$ und $j$ zwei ganze Zahlen von $0$ bis $n$. Du musst sicherstellen, dass die Anzahl deiner Anfragen $1024$ nicht überschreitet. Als Antwort erhältst du eine ganze Zahl $k$ mit $p_k=|p_i-p_j|$.

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

$$!\ p_0\ p_1\ \ldots\ p_n$$

Dabei ist $p$ die Permutation, die du melden möchtest.

Vergiss nach einer Anfrage oder der Meldung der Antwort nicht, einen Zeilenumbruch auszugeben und den Ausgabestrom zu leeren.

In dieser Aufgabe ist der Interaktor adaptiv. Das bedeutet, dass sich die Permutation $p$ abhängig von deinen Anfragen ändern kann, solange sie den zuvor gestellten Anfragen nicht widerspricht.

Beispiele

Beispielinteraktion 1

Lesen:

1
3

Schreiben:

? 2 2

Lesen:

1

Schreiben:

? 0 3

Lesen:

3

Schreiben:

! 2 0 3 1

Testwerkzeug: Ein Testwerkzeug hilft den Teilnehmenden beim Entwickeln und Testen ihrer Lösungen. Du kannst es aus den Anhängen herunterladen. Ein Aufruf mit der Option -h sollte seine Verwendung beschreiben. Das Testwerkzeug implementiert nur einige Testszenarien und einen Teil der Funktionen des tatsächlichen Bewertungsprogramms.