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