Pac-Man 2.0

Description:

Input:

The first line contains four integers $$$n$$$, $$$m$$$, $$$q$$$ and $$$s$$$ ($$$2 \le n \le 15$$$; $$$n \le m \le n(n-1)$$$; $$$1 \le q \le 5000$$$; $$$1 \le s \le n$$$) — the number of safe zones, the number of pathways, the number of goals and the index of the starting safe zone, respectively.

The second line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \le a_i \le 10^9$$$), where $$$a_i$$$ is the initial number of pellets in the $$$i$$$-th safe zone (and the number of pellets that spawn in the $$$i$$$-th safe zone when the last pellet in the world is collected).

Then $$$m$$$ lines follow, each line contains two integers $$$v_i$$$ and $$$u_i$$$ ($$$1 \le v_i, u_i \le n$$$; $$$v_i \ne u_i$$$) denoting a one-directional pathway from the safe zone $$$v_i$$$ to the safe zone $$$u_i$$$. Each ordered pair $$$(v_i, u_i)$$$ appears in this section at most once (there are no multiple pathways from $$$v_i$$$ to $$$u_i$$$), and it is possible to reach every safe zone from every other safe zone using these pathways.

The last line contains $$$q$$$ integers $$$C_1$$$, $$$C_2$$$, ..., $$$C_q$$$ ($$$1 \le C_i \le 10^{15}$$$), where $$$C_i$$$ is the minimum number of pellets the player has to collect in order to fulfil the $$$i$$$-th goal.

Output:

For each goal $$$i$$$, print one integer — its difficulty (the minimum number of times the player has to traverse along some pathway in order to collect at least $$$C_i$$$ pellets).

Sample Input:

3 4 2 1
3 1 2
1 2
2 1
1 3
3 1
5 8

Sample Output:

1
3

Sample Input:

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

Sample Output:

2
6
10
13

Sample Input:

4 4 3 3
2 3 1 4
3 4
4 1
1 2
2 3
13 42 1337

Sample Output:

3
13
401

Note:

Consider the first test. In order to collect $$$5$$$ pellets, the player should collect $$$3$$$ pellets in the safe zone $$$1$$$ (which is starting), move to zone $$$3$$$, collect $$$2$$$ pellets there.

In order to collect $$$8$$$ pellets, the player should collect $$$3$$$ pellets in the safe zone $$$1$$$, go to $$$2$$$, collect $$$1$$$ pellet, go to $$$1$$$ without getting pellets, go to $$$3$$$, collect $$$2$$$ pellets. Now the last pellet in the world is collected, so they are respawned. The player can collect $$$2$$$ pellets in the safe zone $$$3$$$ and now the number of collected pellets is $$$8$$$.

Consider the second test.

In order to collect $$$7$$$ pellets let's do the following: $$$2(+3) \rightarrow 3(+2) \rightarrow 4(+2)$$$. In such a way $$$7$$$ pellets were collected.

In order to collect $$$14$$$ pellets let's do the following: $$$2(+3) \rightarrow 3(+2) \rightarrow 1(+1) \rightarrow 4(+2) \rightarrow 5(+1)$$$ respawn of pellets $$$5(+1) \rightarrow 4 (+2) \rightarrow 2(+3)$$$. In such a way $$$15$$$ pellets were collected.

In order to collect $$$23$$$ pellets let's do the following: $$$2(+3) \rightarrow 3(+2) \rightarrow 1(+1) \rightarrow 4(+2) \rightarrow 5(+1)$$$ respawn of pellets $$$5(+1) \rightarrow 4(+2) \rightarrow 2(+3) \rightarrow 3(+2) \rightarrow 1(+1)$$$ respawn of pellets $$$1(+1) \rightarrow 4(+2) \rightarrow 2(+3)$$$. In such a way $$$24$$$ pellets were collected.