Задача F. Кампус

Автор:Центральная предметно-методическая комиссия   Ограничение времени:1 сек
Входной файл:building.in   Ограничение памяти:256 Мб
Выходной файл:building.out  
Максимальный балл:100  

Условие

Новое здание кампуса Университета Байтбурга имеет n этажей, пронумерованных снизу вверх от 1 до n. Комнаты студентов расположены в нескольких подъездах.

В каждом подъезде на этажах, номер которых кратен числу k, расположено по x комнат, а на остальных этажах расположено по y комнат.

Комнаты внутри каждого подъезда пронумерованы последовательными натуральными числами. Номера комнат на первом этаже имеют наименьшие значения в этом подъезде, затем следуют номера комнат на втором этаже, и так далее. Комнаты в первом подъезде пронумерованы, начиная с 1, в каждом следующем подъезде нумерация комнат начинается с числа, следующего после максимального номера комнаты в предыдущем подъезде.

На рис.1 показаны номера комнат в здании с n=7 этажами, 3 подъездами, и параметрами k = 3, x = 2, y = 3.

Подъезд 1Подъезд 2Подъезд 3
7 этаж17, 18, 1936, 37, 3855, 56, 57
6 этаж15, 1634, 3553, 54
5 этаж12, 13, 1431, 32, 3350, 51, 52
4 этаж9, 10, 1128, 29, 3047, 48, 49
3 этаж7, 826, 2745, 46
2 этаж4, 5, 623, 24, 2542, 43, 44
1 этаж1, 2, 320, 21, 2239, 40, 41
Рис. 1. Пример нумерации комнат в здании.

Для организации расселения студентов администрация кампуса должна по номеру комнаты оперативно определять этаж, на котором она находится.

Требуется написать программу, которая по заданным числам n, k, x и y, а также по номерам комнат, определяет для каждой комнаты, на каком этаже она находится.

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

Первая строка входного файла содержит натуральные числа n, k, x и y. Соседние числа разделены ровно одним пробелом.

Вторая строка входного файла содержит натуральное число q  — количество номеров комнат, для которых требуется определить этаж.

Третья строка содержит q целых чисел a1, a2, ..., aq  — номера комнат. Можно считать, что в здании так много подъездов, что все комнаты с заданными номерами существуют.

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

Требуется вывести q чисел, по одному на строке. Для каждого номера комнаты во входном файле требуется вывести номер этажа, на котором она находится.

Ограничения

1 ≤ n ≤ 109, 1 ≤ x, y ≤ 109, 1 ≤ q ≤ 1000, 1 ≤ ai ≤ 1018

Описание подзадач и системы оценивания

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

Подзадача Баллы Дополнительные ограничения Необходимые подзадачи
n, x, yq, ai
1311 ≤ n ≤ 10,

1 ≤ x, y ≤ 10
q = 1,

1 ≤ ai ≤ 100
2191 ≤ n ≤ 107,

1 ≤ x, y ≤ 109
q = 1,

1 ≤ ai ≤ 107
1
3161 ≤ n ≤ 109,

1 ≤ x, y ≤ 109,

x = y
1 ≤ q ≤ 1000,

1 ≤ ai ≤ 1018
4341 ≤ n ≤ 109,

1 ≤ x, y ≤ 109
1 ≤ q ≤ 1000,

1 ≤ ai ≤ 1018
1,2,3

Получение информации о результатах окончательной проверки

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

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

Входной файл (building.in) Выходной файл (building.out)
1
7 3 2 3
4
1 19 20 50
1
7
1
5

0.045s 0.008s 15