Задача D. Мембрана

Высокий и блондин шли по зданию быстрым шагом, Кеша едва успевал за ними.

— Ну вот, сейчас посмотришь, чем Виктор занимается. Он тоже программист, – блондин подвел Кешу к монитору. На экране медленно перемещались и поворачивались фигурки, хорошо знакомые каждому, кто играл в «Тетрис».

— Оригинальная заставка, – сказал Кеша.

— Это не заставка. Это робот мембрану собирает. А Виктору программу для него надо написать. Чтобы лучше собирал. Оптимальным образом. И быстро. Вот кстати, программист, – блондин потянул Кешу за рукав, – может, напишешь? Посмотрим, что ты умеешь.

— Нет, для начала задачка попроще. У робота уже есть программа, которая позволяет ему выбирать оптимальное решение для каждого шага. И надо понять, что получается в результате его работы.

Мембрана, которую собирает робот, должна иметь размеры N клеток в длину и M клеток в ширину. Существует 5 типов деталей (см. рис.). Робот последовательно берет детали, которых всего D штук; его задача – уложить их так, чтобы во внутренней части мембраны не было пустых клеток. Можно считать, что эти D деталей расположены друг за другом и образуют очередь.

Рис. 1

Действия робота таковы. Первую деталь робот пробует уложить вплотную к верхней границе заготовки в том положении, в котором она (деталь) находится изначально (см. рис. 1). Если деталь удалось положить, то робот берет следующую деталь из очереди, и пытается поместить ее на заготовку со смещением на одну клетку вниз от верхней границы. Если это не удается (могут образоваться пустые клетки), он вновь смещает деталь вниз на одну клетку, поворачивая ее при этом на 90⁰ против часовой стрелки, и повторяет попытку. Такое «движение» вниз продолжается до тех пор, пока деталь не выходит за нижнюю границу мембраны. Когда деталь вышла за границу мембраны, то робот сдвигает деталь вверх так, чтобы она касалась нижней границы и предпринимает очередную попытку уложить деталь. Затем в случае неудачи робот будет перемещать деталь уже вверх, по-прежнему поворачивая ее на 90⁰ против часовой стрелки. При пересечении верхней границы направление движения вновь сменится. Если деталь не удается положить за M попыток, то робот помещает ее в конец очереди (в том положении, в котором она оказалась) и берет следующую деталь из начала очереди. Вновь взятую деталь он попытается положить со смещением на одну клетку по направлению движения. (Иллюстрации приводятся ниже, для примера входного файла.)

Конечно, вполне может произойти, что какие-то детали в принципе не будут уложены. Робот прекращает укладывать детали либо когда очередь опустеет, либо, когда в результате очередного прохода по всей очереди ни одна из деталей не была помещена на заготовку.

Ваша задача – определить, сколько и каких деталей не удастся разместить на заготовке мембраны.

Примечание. Деталь должна всегда помещаться на заготовку мембраны целиком.

Формат входного файла input.txt

Первая строка – целые числа N (3<=N<=200), M (3<=M<=10), D (1<=D<=100) через пробел. N – длина заготовки мембраны в клетках в длину, M – длина заготовки мембраны в клетках в ширину, D – количество деталей в очереди.

Вторая строка – D целых чисел от 1 до 5 через пробел – очередь деталей с указанием их типов.

Формат выходного файла output.txt

Первая строка – пять целых чисел через пробел. Первое число – количество деталей типа 1, которые не были помещены на заготовку. Второе число – количество деталей типа 2, которые не были помещены на заготовку. Третье, четвертое и пятое числа – количества деталей типов 3, 4 и 5 соответственно, которые не были помещены на заготовку.