Þetta verkefni er gagnvirkt. Eftir að hver lína er prentuð út þarftu að tæma úttaksbiðminnið (flush). Þú getur notað cout << flush í C++, System.out.flush() í Java og sys.stdout.flush() í Python. Þú verður að fylgja leiðbeiningunum í kaflanum Samskipti í hvívetna; annars gætirðu fengið niðurstöður eins og rangt svar (wrong answer), tímatakmarki náð (time limit exceeded) eða annað.

Þar sem vinnan í námunni er erfið og tímafrek ákváðu dvergarnir að leita sér aðstoðar við að sjálfvirknivæða hluta af verkefnum sínum. Núverandi verkefni þeirra er að flokka $N$ steindir (auðkenndar með tölum frá $1$ til $N$) í mismunandi flokka. Til að aðstoða við þetta hefur Verkamaðurinn Dvergur sett upp nýtt færiband. Dvergarnir geta bætt sýnum af steindum fremst á færibandið og fjarlægt þau aftast af því (þ.e. fjarlægt þær steindir sem voru settar fyrst á).

Því miður hefur þetta færiband engan þekkingargrunn, svo það getur ekki greint flokk neinnar steindar sem á því er. Hins vegar hefur það annan nytsamlegan eiginleika: það sýnir hversu margir ólíkir flokkar steinda eru á færibandinu hverju sinni. Þetta reynist nægja fyrir námuna, því dvergarnir þurfa ekki að vita flokk hverrar steindar: þeir þurfa bara að aðgreina steindirnar í hrúgur af sama flokki.

Geturðu hjálpað dvergunum að leysa þetta verkefni með því að nota færibandið?

Samskipti

Flokkar steindanna eru ákveðnir í upphafi og ráðast ekki af fyrirspurnunum sem gerðar eru.

Lestu fyrst línu sem inniheldur eina heiltölu $N$, fjölda steinda sem á að flokka. Síðan getur þú framkvæmt aðgerðir af eftirfarandi tveimur gerðum:

• + id — steind með auðkennið id er bætt fremst á færibandið.
• - — steindin aftast á færibandinu er fjarlægð. Ef færibandið er tómt gerist ekkert.

Eftir hverja aðgerð skrifar færibandið út eina línu sem inniheldur fjölda ólíkra flokka sem eru á því í augnablikinu.

Til að skrifa út svarið skaltu fyrst prenta línu sem inniheldur ! ásamt $k$, sem er fjöldi ólíkra flokka í námunni. Prentaðu síðan $k$ línur, þar sem hver lína lýsir einum flokki. Hver lína á að innihalda tölu $c_i$ og þar á eftir $c_i$ auðkenni steinda í þeim flokki. Hver af steindunum $N$ verður að koma fyrir í nákvæmlega einum flokki. Þú mátt skrifa út flokkana og steindirnar innan hvers flokks í hvaða röð sem er.

Mundu að tæma úttaksbiðminnið (flush) eftir hverja aðgerð og eftir að svarið er skrifað. Mundu að hafa bil á milli talna og táknanna +, -, !. Þú verður að lesa öll gögn frá samskiptaforritinu.

Takmarkanir

$1 \le N \le 500$, þú getur framkvæmt í mesta lagi $35\,000$ aðgerðir.

Dæmi

Inntak 1

3
1
2
2
2

Úttak 1

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

Athugasemd

Í fyrsta dæmaprófinu er $N = 3$ og flokkar steindanna $1, 2, 3$ eru $1, 2, 1$ í þessari röð.

Staðbundin prófun

Í hlutanum Files finnurðu A.zip sem inniheldur dæmapróf og prófara grader.cpp. Til að prófa lausnina þína skaltu þýða hana og senda síðan nafn prófsins og keyrsluskrána þína í þýdda ./grader forritið:

./grader [test] [executable]

Til dæmis: ./grader 0b.in ./abc

Ekki er tryggt að dæmaprófarinn hegði sér nákvæmlega eins og sá opinberi. Hvorugur þeirra er þó aðlögunarhæfur (adaptive).