409679: GYM103678 B Бернард и парад поездов
Description
Бернард очень любит поезда. Он часто приходит на железнодорожную станцию, поэтому знает расписание всех поездов. На станции есть $$$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