409679: GYM103678 B Бернард и парад поездов

B. Бернард и парад поездовограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Бернард очень любит поезда. Он часто приходит на железнодорожную станцию, поэтому знает расписание всех поездов. На станции есть $$$N$$$ путей.

На первый путь поезд прибывает в $$$X$$$ минут, на второй путь в $$$X+1$$$ минут, на $$$i$$$-й путь поезд прибывает в $$$X+i-1$$$ минут $$$(1 \le i \le N)$$$. Каждый из поездов имеет период — время, через которое поезд снова прибудет на свой путь. У поезда на $$$i$$$-м пути период равен $$$K+i-1$$$ минут. Таким образом, поезд на первом пути будет на станции в моменты времени $$$X$$$, $$$X+K$$$, $$$X+2\cdot K$$$, $$$...$$$, поезд на втором пути в моменты времени $$$X + 1$$$, $$$X + K + 2$$$, $$$X+2\cdot K + 3$$$, $$$...$$$, а поезд на $$$i$$$-м пути в моменты времени $$$X + i - 1$$$, $$$(X + i - 1) + (K + i - 1)$$$, $$$(X + i - 1) + 2\cdot (K + i - 1)$$$, и т.д.

Самое любимое занятие Бернарда — наблюдать за парадом поездов. Парадом поездов он называет такое событие, когда поезда поочерёдно прибывают на станцию каждую минуту. В одну минуту прибывает поезд на первый путь, в следующую — на второй и т.д. Формально, парад поездов — это такой промежуток времени, который начинается в $$$Y$$$ минут, заканчивается в $$$Y + N - 1$$$ минут, и в $$$(Y + i - 1)$$$-ю минуту на станцию прибывает поезд на $$$i$$$-й путь.

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

Входные данные

Первая строка входных данных содержит три целых числа $$$N$$$, $$$X$$$, $$$K$$$ ($$$1 \le N \le 10^9$$$, $$$1 \le X \le 10^9$$$, $$$N \le K \le 10^9$$$) — количество путей на железнодорожной станции, время прибытия первого поезда и период первого поезда.

Вторая строка содержит единственное целое число $$$Q$$$ ($$$1 \le Q \le 10^5)$$$.

Каждая из следующих $$$Q$$$ строк содержит два целых числа $$$L$$$ и $$$R$$$ ($$$1 \le L \le R \le 10^{18}$$$) — начало и конец отрезка времени, когда Бернард может быть на станции.

Выходные данные

Выведите $$$Q$$$ строк. Каждая строка должна содержать единственное число — количество парадов поездов, которое увидит Бернард, если будет на станции в соответствующий отрезок времени.

Система оценки

Группа	Доп. ограничения	Баллы	Требуемые подзадачи	Тип проверки
$$$1$$$	$$$Q, R \le 1000, N = 1$$$	$$$5$$$	—	Полная
$$$2$$$	$$$N = 1$$$	$$$7$$$	$$$1$$$	Полная
$$$3$$$	$$$N \le 2$$$	$$$7$$$	$$$1-2$$$	Полная
$$$4$$$	$$$N, R \le 1000, Q = 1$$$	$$$10$$$	$$$1$$$	Полная
$$$5$$$	$$$N, R \le 1000$$$	$$$16$$$	$$$1, 4$$$	Полная
$$$6$$$	$$$N \le 10, K \le 50 $$$	$$$25$$$	—	Полная
$$$7$$$	—	$$$30$$$	$$$1-6$$$	Полная

ПримерВходные данные

2 7 3
4
7 8
1 20
15 19
1 1000000000000000000

Выходные данные

1
2
0
83333333333333333