Бұл интерактивті есеп. Әр жолды шығарғаннан кейін шығыс буферін тазарту (flush) қажет. C++ тілінде cout << flush, Java тілінде System.out.flush(), ал Python тілінде sys.stdout.flush() қолдануға болады. «Өзара әрекеттесу» бөліміндегі нұсқауларды қатаң сақтауыңыз керек; әйтпесе қате жауап (wrong answer), уақыт шегінен асып кету (time limit exceeded) немесе басқа да вердикттер алуыңыз мүмкін.
Шахтадағы жұмыс ауыр әрі көп уақытты алатындықтан, ергежейлілер кейбір тапсырмаларын автоматтандыру үшін көмек сұрауды жөн көрді. Олардың қазіргі тапсырмасы — $N$ минералды ($1$-ден $N$-ге дейінгі сандармен белгіленген) әртүрлі кластарға жіктеу. Осыған көмектесу үшін Жұмысшы Ергежейлі жаңа конвейер таспасын орнатты. Ергежейлілер минерал үлгілерін таспаның басына қосып, оларды соңынан алып тастай алады (яғни, ең ерте қосылған минералдарды алып тастайды).
Өкінішке орай, бұл конвейер таспасының білім базасы жоқ, сондықтан ол өзіндегі ешбір минералдың класын анықтай алмайды. Дегенмен, оның басқа пайдалы мүмкіндігі бар: ол қазіргі уақытта таспада минералдардың қанша түрлі класы бар екенін көрсетеді. Бұл шахта үшін жеткілікті болып шықты, өйткені ергежейлілерге әр минералдың класын білудің қажеті жоқ: оларға тек минералдарды бір класты үйінділерге бөлу жеткілікті.
Конвейер таспасын пайдаланып, ергежейлілерге осы тапсырманы шешуге көмектесе аласыз ба?
Өзара әрекеттесу
Минералдардың кластары бастапқыда бекітілген және жасалған сұрауларға тәуелді емес.
Алдымен жіктелетін минералдар санын білдіретін бір бүтін сан $N$ бар жолды оқыңыз. Содан кейін келесі екі түрдегі операцияларды орындай аласыз:
+ id— идентификаторыidболатын минерал конвейер таспасының басына қосылады.-— конвейер таспасының соңындағы минерал алып тасталады. Егер таспа бос болса, ештеңе болмайды.
Әр операциядан кейін конвейер таспасы қазіргі уақытта ондағы әртүрлі кластардың санын қамтитын бір жолды шығарады.
Жауапты шығару үшін алдымен ! таңбасы бар, одан кейін шахтадағы әртүрлі кластар саны болып табылатын $k$ саны бар жолды шығарыңыз. Содан кейін әрқайсысы бір класты сипаттайтын $k$ жолды шығарыңыз. Әр жолда $c_i$ саны және одан кейін сол кластағы минералдардың $c_i$ идентификаторы болуы керек. $N$ минералдың әрқайсысы дәл бір класта кездесуі тиіс. Кластарды және әр класс ішіндегі минералдарды кез келген ретпен шығаруға болады.
Әр операциядан кейін және жауапты жазғаннан кейін шығыс буферін тазартуды (flush) ұмытпаңыз. Сандар мен +, -, ! таңбаларының арасына бос орын қоюды ұмытпаңыз. Сіз интерактордан барлық деректерді оқуыңыз керек.
Шектеулер
$1 \le N \le 500$, сіз ең көбі $35\,000$ операция орындай аласыз.
Мысалдар
Кіріс 1
3 1 2 2 2
Шығыс 1
+ 1 + 2 + 3 - ! 2 2 1 3 1 2
Ескертпе
Бірінші мысал тестінде $N = 3$ және $1, 2, 3$ минералдарының кластары сәйкесінше $1, 2, 1$ болады.
Жергілікті тестілеу
Files бөлімінен мысал тесттері мен grader.cpp грейдері бар A.zip мұрағатын таба аласыз. Шешіміңізді тексеру үшін оны компиляциялап, содан кейін тест атауы мен орындалатын файлыңызды компиляцияланған ./grader бағдарламасына беріңіз:
./grader [test] [executable]
Мысалы: ./grader 0b.in ./abc
Мысал грейдерінің ресми грейдермен бірдей жұмыс істейтініне кепілдік берілмейді. Дегенмен, екеуі де адаптивті емес.