Бернард очень любит поезда. Он часто приходит на железнодорожную станцию, поэтому знает расписание всех поездов. На станции есть $$$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$$$ отрезков времени, но он не может определиться, в какой. Чтобы принять решение, когда ему следует прийти на станцию, Бернард решил для каждого из отрезков времени узнать, сколько раз он сможет увидеть парад поездов. Помогите Бернарду с этой непростой задачей.