22146번 - Социофоб 다국어

Далеко не всем людям приятно постоянно находиться в толпе. Многие любят уединение и даже готовы за него платить. Именно поэтому ОАО «Радостные Железные Дороги» ввело на своем сайте продажи билетов новую услугу, называющуюся «Социофоб». Услуга необходима для того, чтобы дать возможность каждому пассажиру ехать в купе с наименьшим возможным количеством соседей. Суть ее заключается в следующем.

Пусть билеты продаются в некоторый вагон, в котором часть купе уже заполнена. Если в какой-то момент в этот вагон покупает билет очередной пассажир, ему продается место в самом незаполненном купе, то есть в купе, в котором количество людей не больше, чем во всех остальных. Если таких купе несколько, то выбирается купе с наименьшим номером. Если же пассажир из какого-то купе сдает свой билет, после чего разница между количеством людей в этом купе и в наиболее заполненном купе становится равной хотя бы двум, то из наиболее заполненного купе на освободившееся место пересаживается пассажир, который раньше других купил билет, то есть пассажир с наименьшим номером. Если наиболее заполненных купе несколько, то из них выбирается купе, ближайшее к тому, в котором был сдан билет. А если и таких несколько, то выбирается купе с наименьшим номером.

По данным о том, как пассажиры покупали и сдавали билеты, требуется вывести итоговое распределение пассажиров по купе. Гарантируется, что каждый раз когда какой-либо пассажир покупает билет, в вагоне есть хотя бы одно свободное место.

В первой строке заданы три целых числа m, n и k (1 ≤ m ≤ 200000, 1 ≤ n, k ≤ 50000) — количество операций покупки или сдачи билетов, количество купе в вагоне и количество мест в каждом купе, соответственно. В следующих m строках задана последовательность покупок и сдач билетов.

Если строка содержит единственный символ «+», то это означает, что в вагон купил билет очередной пассажир, причём номер пассажира равен порядковому номеру плюса во входном файле. Если строка имеет вид «− id», где id — целое число от одного до m, то это означает, что пассажир с номером id сдал свой билет. Гарантируется, что на этот момент у этого пассажира есть билет.

Выведите n строк, где первое число i-й строки l_i означает, сколько билетов продано в i-ом купе, далее следуют l_i чисел — номера пассажиров, которые будут ехать в i-ом купе, выведенные в порядке возрастания. Гарантируется, что ответ всегда существует.