Задача H. Доска объявлений ≡

Условие

На входе в университет висит огромная прямоугольная доска объявлений размером h × w (h — высота, а w — ширина). Доска — это место, где вывешиваются всевозможные объявления о ближайших контестах, изменениях в меню столовой и другая важная информация.

Первого сентября доска была пустой. Один за одним добавлялись объявления.

Каждое объявление — это полоска бумаги единичной высоты. Более точно, i-ое объявление — это прямоугольник размером 1 × w_i.

Когда кто-либо добавляет новое объявление на доску, он всегда выбирает самую высокую возможную позицию для объявления. Среди всех возможных самых высоких позиций он выбирает самую левую.

Если для нового объявления нет места, оно не помещается на доску.

Даны размеры доски и объявлений, ваша задача — найти номера рядов, в которые будут помещены объявления.

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

Первая строка входного файла содержит три целых числа h, w, и n — размеры доски и количество объявлений.

Каждая из следующих n строк содержит целое число w_i — ширину i-ого объявления.

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

Для каждого объявления (в порядке, данном во входном файле) выведите одно число — номер ряда, в который помещается объявление. Ряды занумерованы от 1 до h, начиная с верхнего ряда. Если объявление не может быть помещено на доску, выведите "-1" для этого объявления.

Ограничения

1 ≤ h, w ≤ 10⁹, 1 ≤ n ≤ 200000, 1 ≤ w_i ≤ 10⁹.

Примеры тестов

3 5 5
2
4
3
3
3

1
2
1
3
-1