На далёком континенте в бескрайней степи жило племя Морьтонов. Они пасли лошадей, овец, а также совершали набеги на соседние племена. После очередного набега хан Удирдагч рассматривал награбленное, когда на его глаза неожиданно попался необычный свиток. Он рассказывал о далекой стране Леку-Десирагаррия, лежащей на другом конце континента и обладающей несметными богатствами. Вдохновившись этими историями, военачальник решил отправиться в завоевательный поход.
Континент можно представить в виде прямоугольника, разбитого на равные квадратные ячейки. Ставка хана располагается в клетке $$$(0, M)$$$, а Леку-Десирагаррия — в клетке $$$(N, 0)$$$. Координаты задаются в виде (<номер строки>, <номер столбца>). Строки нумеруются сверху вниз, а столбцы слева направо.
Удирдагч хочет послать как можно больше отрядов. При этом, чтобы они не перебили друг друга, каждый из них должен идти уникальным маршрутом, то есть для любых двух отрядов должна быть хотя бы одна ячейка, в которой остановился переночевать первый отряд, но не останавливался второй.
Каждый отряд за время дневного перехода может переместиться двумя способами: на $$$A$$$ клеток влево и на $$$B$$$ клеток вниз, либо на $$$A$$$ клеток вниз и $$$B$$$ клеток влево. Клетка считается посещённой, только если в ней отряд останавливается на ночёвку.
Естественно, вождю потребовалось узнать, какое наибольшее количество отрядов могут добраться до Леку-Десирагаррии.
Продумывая маршруты, военачальник открыл нарисованную на свитке карту континента и увидел на ней $$$Q$$$ городов, которые было бы неплохо по пути ограбить. Поэтому для каждого города из списка ему необходимо знать, сколько отрядов пройдут через содержащую этот город ячейку, а затем доберутся до конечной точки маршрута по описанным выше правилам. На основе этой информации он самостоятельно примет решение о том, стоит ли нападать на город или лучше просто переночевать недалеко от него.
Помимо этого на карте присутствует крупнейший город на континенте Дэлхийн-Тов, про который хан может решить, что его отряды по соображениям безопасности не должны останавливаться в одной клетке с этим городом.
Помогите хану определить количество отрядов, которое тот может собрать в поход, попутно ответив на вопросы о количестве отрядов, которые посетят города из списка.
В первой строке вводятся четыре целых числа $$$N$$$, $$$M$$$, $$$A$$$ и $$$B$$$ ($$$1 \le N, M \le 10^8$$$, $$$0 \le B \lt A \le \max(N, M)$$$) — размеры континента и описание перехода отрядов хана.
Во второй строке вводится целое число $$$C$$$ ($$$C \in \{0, 1\}$$$) — количество ячеек, которые хан хочет избегать. Если $$$C = 1$$$, то в этой же строке также вводятся два целых числа $$$r_c$$$, $$$c_c$$$ ($$$0 \le r_c \le N,\ 0 \le c_c \le M$$$) — координаты ячейки, содержащей город Дэлхийн-Тов.
В третьей строке вводится единственное целое число $$$Q$$$ ($$$1 \le Q \le 10^5$$$) — количество промежуточных городов, интересующих хана.
В последующих $$$Q$$$ строках вводятся по два целых числа $$$r_i$$$, $$$c_i$$$ ($$$0 \le r_i \le N,\ 0 \le c_i \le M$$$) — координаты ячейки, содержащей $$$i$$$-й город из списка.
Гарантируется, что от ставки хана до Леку-Десирагаррии можно добраться за не более чем $$$5\cdot 10^6$$$ дней.
В первой строке выведите единственное число — количество различных путей из ячейки $$$(0, M)$$$ в ячейку $$$(N, 0)$$$ с учётом возможного запрета на остановку в ячейке $$$(r_c, c_c)$$$.
В последующих $$$Q$$$ строках выведите по одному числу: в $$$i$$$-й строке выведите количество различных путей, проходящих через ячейку $$$(r_i, c_i)$$$ с учётом возможного запрета на остановку в ячейке $$$(r_c, c_c)$$$.
Выведите все ответы по модулю $$$10^9 + 9$$$.
Баллы за каждую подгруппу начисляются только в случае прохождения всех тестов этой подгруппы и всех тестов всех необходимых подгрупп.
| Подгруппа | Дополнительные ограничения | Баллы | Необходимые подгруппы | |||
| $$$N,\ M$$$ | $$$A,\ B$$$ | $$$C$$$ | $$$Q$$$ | |||
| $$$0$$$ | Тесты из условия | $$$0$$$ | — | |||
| $$$1$$$ | $$$N, M \le 100$$$ | — | $$$C = 0$$$ | $$$Q = 0$$$ | $$$6$$$ | $$$0$$$ |
| $$$2$$$ | $$$N, M \le 100$$$ | — | $$$C = 0$$$ | $$$Q \le 100$$$ | $$$6$$$ | $$$0, 1$$$ |
| $$$3$$$ | $$$N, M \le 100$$$ | — | $$$C = 1$$$ | $$$Q \le 100$$$ | $$$10$$$ | $$$0$$$ – $$$2$$$ |
| $$$4$$$ | $$$N, M \le 10^4$$$ | $$$A, B \le 100$$$ | $$$C = 0$$$ | $$$Q \le 10^4$$$ | $$$6$$$ | $$$0$$$ – $$$2$$$ |
| $$$5$$$ | $$$N, M \le 10^4$$$ | $$$A, B \le 100$$$ | $$$C = 1$$$ | $$$Q \le 10^4$$$ | $$$7$$$ | $$$0$$$ – $$$4$$$ |
| $$$6$$$ | — | $$$A = 1, B = 0$$$ | $$$C = 0$$$ | — | $$$10$$$ | $$$0$$$ |
| $$$7$$$ | — | $$$A = 1, B = 0$$$ | $$$C = 1$$$ | — | $$$5$$$ | $$$0, 6$$$ |
| $$$8$$$ | — | $$$A = 2, B = 1$$$ | $$$C = 0$$$ | — | $$$10$$$ | $$$0$$$ |
| $$$9$$$ | — | $$$A = 2, B = 1$$$ | $$$C = 1$$$ | — | $$$5$$$ | $$$0, 8$$$ |
| $$$10$$$ | — | — | $$$C = 0$$$ | — | $$$12$$$ | $$$0, 1, 2, 4, 6, 8$$$ |
| $$$11$$$ | — | — | $$$C = 1$$$ | $$$Q = 0$$$ | $$$8$$$ | $$$0, 1$$$ |
| $$$12$$$ | — | — | $$$C = 1$$$ | — | $$$15$$$ | $$$0$$$ – $$$11$$$ |
8 10 2 11 2 9102 92 61 87 20 104 51 68 04 28 3
10 0 6 10 6 10 6 0 10 1 0
