Ce problème est interactif. Après avoir affiché chaque ligne, vous devez vider le tampon de sortie (flush). Vous pouvez utiliser cout << flush en C++, System.out.flush() en Java et sys.stdout.flush() en Python. Vous devez suivre strictement les instructions de la section Interaction ; sinon, vous risquez de recevoir des verdicts tels que réponse erronée (wrong answer), limite de temps dépassée (time limit exceeded) ou autres.

Parce que le travail dans la mine est dur et prend beaucoup de temps, les nains ont décidé de chercher de l'aide pour automatiser certaines de leurs tâches. Leur tâche actuelle consiste à classer $N$ minéraux (identifiés par des numéros de $1$ à $N$) dans différentes classes. Pour les aider, le Nain Ouvrier a installé un nouveau tapis roulant. Les nains peuvent ajouter des échantillons de minéraux au début du tapis et les retirer à sa fin (c'est-à-dire retirer les minéraux qui ont été ajoutés le plus tôt).

Malheureusement, ce tapis roulant n'a pas de base de connaissances, il ne peut donc identifier la classe d'aucun minéral qui s'y trouve. Cependant, il possède une autre fonctionnalité utile : il affiche combien de classes distinctes de minéraux se trouvent actuellement sur le tapis. Il s'avère que cela suffit pour la mine, car les nains n'ont pas besoin de connaître la classe de chaque minéral : ils ont juste besoin de séparer les minéraux en tas de la même classe.

Pouvez-vous aider les nains à résoudre cette tâche à l'aide du tapis roulant ?

Interaction

Les classes de minéraux sont fixées au début et ne dépendent pas des requêtes effectuées.

Tout d'abord, lisez une ligne contenant un entier $N$, le nombre de minéraux à classer. Ensuite, vous pouvez effectuer des opérations des deux types suivants :

• + id — le minéral avec l'identifiant id est ajouté au début du tapis roulant.
• - — le minéral à la fin du tapis roulant est retiré. Si le tapis est vide, rien ne se passe.

Après chaque opération, le tapis roulant affiche une ligne contenant le nombre de classes distinctes actuellement présentes sur celui-ci.

Pour afficher la réponse, affichez d'abord une ligne contenant ! suivi de $k$, le nombre de classes distinctes dans la mine. Affichez ensuite $k$ lignes, chacune décrivant une classe. Chaque ligne doit contenir un nombre $c_i$ suivi de $c_i$ identifiants de minéraux de cette classe. Chacun des $N$ minéraux doit apparaître dans exactement une classe. Vous pouvez afficher les classes et les minéraux au sein de chaque classe dans n'importe quel ordre.

N'oubliez pas de vider la sortie (flush) après chaque opération et après avoir écrit la réponse. N'oubliez pas de mettre des espaces entre les nombres et les symboles +, -, !. Vous devez lire toutes les données de l'interacteur.

Contraintes

$1 \le N \le 500$, vous pouvez effectuer au plus $35\,000$ opérations.

Exemples

Entrée 1

3
1
2
2
2

Sortie 1

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

Note

Dans le premier test d'exemple, $N = 3$ et les classes des minéraux $1, 2, 3$ sont respectivement $1, 2, 1$.

Tests locaux

Dans la section Files, vous trouverez A.zip contenant des tests d'exemple et un évaluateur grader.cpp. Pour tester votre solution, compilez-la, puis passez le nom du test et votre exécutable au ./grader compilé :

./grader [test] [executable]

Par exemple : ./grader 0b.in ./abc

L'évaluateur d'exemple n'est pas garanti de se comporter de manière identique à l'officiel. Cependant, aucun des deux n'est adaptatif.