Diese Aufgabe ist interaktiv. Nach der Ausgabe jeder Zeile musst du den Ausgabepuffer leeren (flush). Du kannst cout << flush in C++, System.out.flush() in Java und sys.stdout.flush() in Python verwenden. Du musst die Anweisungen im Abschnitt Interaktion strikt befolgen; andernfalls erhältst du möglicherweise Bewertungen wie falsche Antwort (wrong answer), Zeitlimit überschritten (time limit exceeded) oder andere.

Da die Arbeit in der Mine hart und zeitaufwendig ist, haben die Zwerge beschlossen, Hilfe bei der Automatisierung einiger ihrer Aufgaben zu suchen. Ihre aktuelle Aufgabe besteht darin, $N$ Mineralien (identifiziert durch Zahlen von $1$ bis $N$) in verschiedene Klassen einzuteilen. Um dabei zu helfen, hat Zwerg der Arbeiter ein neues Förderband installiert. Die Zwerge können Mineralproben am Anfang des Bandes hinzufügen und sie am Ende wieder entnehmen (d. h. die Mineralien entnehmen, die am frühesten hinzugefügt wurden).

Leider verfügt dieses Förderband über keine Wissensdatenbank, sodass es die Klasse keines darauf befindlichen Minerals identifizieren kann. Es hat jedoch eine andere nützliche Funktion: Es zeigt an, wie viele verschiedene Klassen von Mineralien sich derzeit auf dem Band befinden. Es stellt sich heraus, dass dies für die Mine völlig ausreicht, da die Zwerge die Klasse jedes einzelnen Minerals gar nicht kennen müssen: Sie müssen die Mineralien lediglich in Haufen derselben Klasse aufteilen.

Kannst du den Zwergen helfen, diese Aufgabe mithilfe des Förderbandes zu lösen?

Interaktion

Die Klassen der Mineralien stehen von Anfang an fest und hängen nicht von den gestellten Anfragen ab.

Lies zuerst eine Zeile mit einer ganzen Zahl $N$ ein, der Anzahl der zu klassifizierenden Mineralien. Danach kannst du Operationen der folgenden zwei Arten ausführen:

• + id — das Mineral mit dem Bezeichner id wird am Anfang des Förderbandes hinzugefügt.
• - — das Mineral am Ende des Förderbandes wird entfernt. Wenn das Band leer ist, passiert nichts.

Nach jeder Operation gibt das Förderband eine Zeile aus, die die Anzahl der verschiedenen Klassen enthält, die sich derzeit darauf befinden.

Um die Antwort auszugeben, gib zuerst eine Zeile mit ! gefolgt von $k$ aus, der Anzahl der verschiedenen Klassen in der Mine. Gib dann $k$ Zeilen aus, die jeweils eine Klasse beschreiben. Jede Zeile muss eine Zahl $c_i$ gefolgt von $c_i$ Mineralbezeichnern dieser Klasse enthalten. Jedes der $N$ Mineralien muss in genau einer Klasse vorkommen. Du kannst die Klassen und die Mineralien innerhalb jeder Klasse in beliebiger Reihenfolge ausgeben.

Denke daran, die Ausgabe nach jeder Operation und nach dem Schreiben der Antwort zu leeren (flush). Denke daran, Leerzeichen zwischen Zahlen und den Symbolen +, -, ! zu setzen. Du musst alle Daten vom Interaktor einlesen.

Einschränkungen

$1 \le N \le 500$, du kannst höchstens $35\,000$ Operationen ausführen.

Beispiele

Eingabe 1

3
1
2
2
2

Ausgabe 1

+ 1
+ 2
+ 3
-
! 2
2 1 3
1 2

Hinweis

Im ersten Beispieltest ist $N = 3$ und die Klassen der Mineralien $1, 2, 3$ sind jeweils $1, 2, 1$.

Lokales Testen

Im Abschnitt Files findest du A.zip mit Beispieltests und einem Grader grader.cpp. Um deine Lösung zu testen, kompiliere sie und übergib dann den Testnamen und deine ausführbare Datei an den kompilierten ./grader:

./grader [test] [executable]

Zum Beispiel: ./grader 0b.in ./abc

Es wird nicht garantiert, dass sich der Beispiel-Grader identisch zum offiziellen verhält. Allerdings ist keiner von beiden adaptiv.