Задача №934. Информационный стенд
В холле 179 школы, есть информационный стенд размером \(H \times W\) (\(H\) – высота, \(W\) – ширина). На этом стенде размещается информация о кружках, изменениях в расписании, победах в олимпиадах, а также другая важная информация.
Первого сентября стенд был пуст. Одно за другим на нем начали появляться объявления, которые потом не снимались.
Каждое объявление представляет собой полоску бумаги единичной высоты. I-ое объявление представляет собой прямоугольник размером \(1 \times W_i\).
Когда кто-либо вешает объявление на стенд, то он старается повесить объявление как можно выше. Среди возможных верхних мест всегда выбирается самое левое. Если подходящего места для объявления не нашлось, то объявление не вешается на стенд. Ваша задача состоит в том, чтобы для каждого объявления определить, как высоко оно будет располагаться (в каком ряду).
Первая строка содержит три целых числа \(H\), \(W\) и \(N\) (\(1 \leq H, W \leq 10^9\); \(1 \leq N \leq 200 000\)) — размеры стенда и количество объявлений. Каждая из следующих N строк содержит по одному целому числу \(W_i\) (\(1 \leq W_i \leq 10^9\)) — ширину \(i\)-го объявления.
Для каждого из объявлений (в порядке следования во входном файле) выведите номер ряда, в котором оно будет размещено. Ряды занумерованы от \(1\) до \(H\) сверху вниз. Если объявление разместить нельзя — выведите «–1».
3 5 5 2 4 3 3 3
1 2 1 3 -1