Denne oppgaven er interaktiv. Etter å ha skrevet ut hver linje må du tømme utdatabufferen (flush). Du kan bruke cout << flush i C++, System.out.flush() i Java og sys.stdout.flush() i Python. Du må følge instruksjonene i delen Interaksjon strengt; ellers kan du få dommer som feil svar (wrong answer), tidsgrense overskredet (time limit exceeded) eller andre.

Fordi arbeidet i gruven er hardt og tidkrevende, bestemte dvergene seg for å søke hjelp til å automatisere noen av oppgavene sine. Deres nåværende oppgave er å klassifisere $N$ mineraler (identifisert med tall fra $1$ til $N$) i forskjellige klasser. For å hjelpe til med dette har Dvergen Arbeideren installert et nytt transportbånd. Dvergene kan legge til prøver av mineraler i begynnelsen av båndet og fjerne dem fra enden (dvs. fjerne mineralene som ble lagt til tidligst).

Dessverre har ikke dette transportbåndet noen kunnskapsbase, så det kan ikke identifisere klassen til noe mineral på det. Det har imidlertid en annen nyttig funksjon: det viser hvor mange forskjellige klasser av mineraler som for øyeblikket befinner seg på båndet. Det viser seg at dette er tilstrekkelig for gruven, ettersom dvergene ikke trenger å vite klassen til hvert mineral: de trenger bare å sortere mineralene i hauger av samme klasse.

Kan du hjelpe dvergene med å løse denne oppgaven ved hjelp av transportbåndet?

Interaksjon

Klassene til mineralene er fastsatt fra starten og avhenger ikke av spørringene som gjøres.

Les først en linje som inneholder ett heltall $N$, antallet mineraler som skal klassifiseres. Deretter kan du utføre operasjoner av følgende to typer:

• + id — mineral med identifikator id legges til i begynnelsen av transportbåndet.
• - — mineralet på slutten av transportbåndet fjernes. Hvis båndet er tomt, skjer ingenting.

Etter hver operasjon skriver transportbåndet ut én linje som inneholder antallet forskjellige klasser som for øyeblikket er på det.

For å skrive ut svaret, skriv først ut en linje som inneholder ! etterfulgt av $k$, som er antallet forskjellige klasser i gruven. Skriv deretter ut $k$ linjer, der hver linje beskriver én klasse. Hver linje skal inneholde et tall $c_i$ etterfulgt av $c_i$ mineralidentifikatorer fra den klassen. Hvert av de $N$ mineralene må forekomme i nøyaktig én klasse. Du kan skrive ut klassene og mineralene innenfor hver klasse i hvilken som helst rekkefølge.

Husk å tømme utdatabufferen (flush) etter hver operasjon og etter å ha skrevet svaret. Husk å sette mellomrom mellom tall og symbolene +, -, !. Du må lese alle data fra interaktoren.

Begrensninger

$1 \le N \le 500$, du kan utføre maksimalt $35\,000$ operasjoner.

Eksempler

Inndata 1

3
1
2
2
2

Utdata 1

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

Forklaring

I den første eksempeltesten er $N = 3$, og klassene til mineralene $1, 2, 3$ er henholdsvis $1, 2, 1$.

Lokal testing

I delen Files finner du A.zip som inneholder eksempeltester og en grader grader.cpp. For å teste løsningen din, kompiler den, og send deretter testnavnet og den kjørbare filen din til den kompilerte ./grader:

./grader [test] [executable]

For eksempel: ./grader 0b.in ./abc

Eksempelgraderen er ikke garantert å oppføre seg identisk med den offisielle. Ingen av dem er imidlertid adaptive.