I. Pac-Man 2.0
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Поликарп разрабатывает новую версию старой видеоигры «Pac-Man». Хотя ему действительно нравилось играть в оригинальную игру, некоторые ее аспекты ему не нравились, поэтому он решил немного изменить правила.

В версии Поликарпа вы играете за Пакмана, и вам нужно собирать точки, разбросанные по игровому миру, избегая при этом опасных призраков (никаких отличий от оригинала пока нет). Поликарпу не понравилось то, что в оригинале не было спасения от призраков, поэтому в его версии игровой мир разделен на $$$n$$$ безопасных зон с $$$m$$$ односторонними путями между ними. Также гарантируется, что Пакман может достичь любой безопасной зоны из любой другой. Поскольку безопасные зоны безопасны, призраки не могут атаковать Пакмана, пока он там, он находится в опасности только во время прохождения путей. Пакман начинает игру в безопасной зоне $$$s$$$.

Все точки разбросаны по безопасным зонам; первоначально $$$i$$$-я безопасная зона содержит $$$a_i$$$ точек (и если Пакман находится в безопасной зоне, он может свободно собирать все точки в ней). Точки исчезают после сбора, но после того, как собрана последняя точка в игровом мире, новые точки появляются в безопасных зонах в том же количестве, что и раньше ($$$a_i$$$ новых точек появляется в $$$i$$$-й зоне). Точки могут быть восстановлены любое количество раз, так что игра по существу бесконечна.

Поликарп уже определил структуру игрового мира и количество точек в каждой безопасной зоне. Теперь он пытается выяснить, достаточно ли сложна игра. В игре есть $$$q$$$ целей, цель $$$i$$$ — собрать по крайней мере $$$C_i$$$ точек с самого начала игры. Поликарп обозначает сложность $$$i$$$-й цели как минимальное количество раз, которое игрок должен пройти путь между безопасными зонами, чтобы собрать $$$C_i$$$ точек (так как только прохождение пути ставит Пакмана в опасность). Если какой-то путь пройден несколько раз, пока Пакман собирает точки, то он включается в ответ столько же раз.

Помогите Поликарпу рассчитать сложность каждой цели!

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

Первая строка содержит четыре целых числа $$$n$$$, $$$m$$$, $$$q$$$ и $$$s$$$ ($$$2 \le n \le 15$$$; $$$n \le m \le n(n-1)$$$; $$$1 \le q \le 5000$$$; $$$1 \le s \le n$$$) — количество безопасных зон, количество путей, количество целей и номер стартовой безопасной зоны соответственно.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \le a_i \le 10^9$$$), где $$$a_i$$$ — начальное количество точек в $$$i$$$-й безопасной зоне (и количество точек, которые появляются в $$$i$$$-й безопасной зоне, когда собрана последняя точка в игровом мире).

Далее следуют $$$m$$$ строк, каждая из которых содержит два целых числа $$$v_i$$$ и $$$u_i$$$ ($$$1 \le v_i, u_i \le n$$$; $$$v_i \ne u_i$$$), обозначающие односторонний путь от безопасной зоны $$$v_i$$$ до безопасной зоны $$$u_i$$$. Каждая упорядоченная пара $$$(v_i, u_i)$$$ появляется в этом разделе не более одного раза (нет нескольких путей от $$$v_i$$$ до $$$u_i$$$), и с помощью этих путей можно достичь каждой безопасной зоны из любой другой безопасной зоны.

Последняя строка содержит $$$q$$$ целых чисел $$$C_1$$$, $$$C_2$$$, ..., $$$C_q$$$ ($$$1 \le C_i \le 10^{15}$$$), где $$$C_i$$$ — минимальное количество точек, которые игрок должен собрать для достижения $$$i$$$-й цели.

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

Для каждой цели $$$i$$$ выведите одно целое число — ее сложность (минимальное количество раз, которое игрок должен пройти по некоторому пути, чтобы собрать хотя бы $$$C_i$$$ точек).

Примеры
Входные данные
3 4 2 1
3 1 2
1 2
2 1
1 3
3 1
5 8
Выходные данные
1
3
Входные данные
5 7 4 2
1 3 2 2 1
2 3
4 2
3 4
3 1
1 4
5 4
4 5
7 14 23 27
Выходные данные
2
6
10
13
Входные данные
4 4 3 3
2 3 1 4
3 4
4 1
1 2
2 3
13 42 1337
Выходные данные
3
13
401
Примечание

Рассмотрим первый пример из условия. Чтобы собрать $$$5$$$ точек, игрок должен собрать $$$3$$$ точки в безопасной зоне $$$1$$$ (стартовая безопасная зона), перейти в зону $$$3$$$, собрать $$$2$$$ точки там.

Для того чтобы собрать $$$8$$$ точек, игрок должен собрать $$$3$$$ точки в безопасной зоне $$$1$$$, перейти в зону $$$2$$$, собрать $$$1$$$ точку, перейти в зону $$$1$$$ без получения точек, перейти в зону $$$3$$$, собрать $$$2$$$ точки. Теперь последние точки в мире собраны, так что они восстанавливаются. Игрок может собрать $$$2$$$ точки в безопасной зоне $$$3$$$ и теперь количество собранных точек составляет $$$8$$$.

Рассмотрим второй пример из условия.

Для того чтобы собрать $$$7$$$ точек игрок должен действовать следующим образом: $$$2(+3) \rightarrow 3(+2) \rightarrow 4(+2)$$$. Таким образом будет собрано $$$7$$$ точек.

Для того чтобы собрать $$$14$$$ точек игрок должен действовать следующим образом: $$$2(+3) \rightarrow 3(+2) \rightarrow 1(+1) \rightarrow 4(+2) \rightarrow 5(+1)$$$ восстановление точек $$$5(+1) \rightarrow 4 (+2) \rightarrow 2(+3)$$$. Таким образом будет собрано $$$15$$$ точек.

Для того чтобы собрать $$$23$$$ точки игрок должен действовать следующим образом: $$$2(+3) \rightarrow 3(+2) \rightarrow 1(+1) \rightarrow 4(+2) \rightarrow 5(+1)$$$ восстановление точек $$$5(+1) \rightarrow 4(+2) \rightarrow 2(+3) \rightarrow 3(+2) \rightarrow 1(+1)$$$ восстановление точек $$$1(+1) \rightarrow 4(+2) \rightarrow 2(+3)$$$. Таким образом будет собрано $$$24$$$ точки.