Pac-Man 2.0
Contest: Kotlin Heroes: Episode 4
Difficulty rating: 2900
Tags: *special, dp

Polycarp is developing a new version of an old video game "Pac-Man". Though he really enjoyed playing the original game, he didn't like some aspects of it, so he decided to alter the rules a bit.

In Polycarp's version, you play as Pac-Man and you have to collect pellets scattered over the game world while avoiding dangerous ghosts (no difference from the original yet). Polycarp didn't like the fact that there was no escape from the ghosts in the original, so, in his version, the game world is divided into $$$n$$$ safe zones with $$$m$$$ one-directional pathways between them — and it is guaranteed that Pac-Man can reach any safe zone from any other. Since safe zones are safe, the ghosts cannot attack Pac-Man while it is there, it is in danger only while traversing the pathways. Pac-Man starts the game in the safe zone $$$s$$$.

All pellets are scattered over the safe zones; initially, the $$$i$$$-th safe zone contains $$$a_i$$$ pellets (and if Pac-Man is in a safe zone, it may freely collect all the pellets in it). The pellets disappear after being collected, but after the last pellet in the game world is collected, new pellets spawn in the safe zones in the same quantity as before ($$$a_i$$$ new pellets spawn in the $$$i$$$-th zone). The pellets can be respawned any number of times, so the game is essentially infinite.

Polycarp has already determined the structure of the game world and the number of pellets in each safe zone. Now he is trying to find out if the game is difficult enough. There are $$$q$$$ goals in the game, the $$$i$$$-th goal is to collect at least $$$C_i$$$ pellets from the beginning of the game. Polycarp denotes the difficulty of the $$$i$$$-th goal as the minimum number of times the player has to traverse a one-directional pathway in order to collect $$$C_i$$$ pellets (since only traversing a pathway puts Pac-Man in danger). If some pathway is traversed multiple times while Pac-Man is collecting the pellets, it is included in the answer the same number of times.

Help Polycarp to calculate the difficulty of each goal!

Input format:
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 format:
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).

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

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.

Example input:
3 4 2 1
3 1 2
1 2
2 1
1 3
3 1
5 8

Example output:
1
3

Example 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

Example output:
2
6
10
13

Editorial:
We will first try to solve two easier versions of this problem. Let's denote $$$\sum a_i$$$ as $$$P$$$ (the total number of pellets in the game world).
Version 1: there is only one goal with $$$C_i = P$$$.
That's quite an easy one, we should visit all the vertices of the graph in minimum number of steps. This can be done with bitmask dynamic programming similar to searching for the Hamiltonian path: let $$$dp_{cur, mask}$$$ be the minimum number of steps to visit vertices from $$$mask$$$ and end up in vertex $$$cur$$$, if we start from vertex $$$s$$$. We are interested in states having full masks, and the minimum of their values is the minimum number of steps required to visit all vertices.
Version 2: all goals have $$$C_i \bmod P = 0$$$.
In this version, we have to traverse the whole graph exactly $$$\frac{C_i}{P}$$$ times. Let's construct a new weighted graph consisting of $$$n$$$ vertices, where the arc from vertex $$$x$$$ to vertex $$$y$$$ has weight equal to the minimum number of steps required to start in vertex $$$x$$$, visit all vertices in the graph, and end up in vertex $$$y$$$. To calculate the weights of these arcs, we can use the dynamic programming approach similar to the solution of Version 1 (the main difference is that we try all starting vertices instead of just $$$s$$$).
After we construct this new graph, our problem is to find the shortest path consisting of exactly $$$\frac{C_i}{P}$$$ edges in it. This problem can be solved with an approach similar to fast matrix exponentiation (you may read about it here: https://cp-algorithms.com/graph/fixed_length_paths.html) in $$$O(n^3 \log C)$$$ for each query; though since we have up to $$$5000$$$ queries, we should speed it up by precalculating $$$[M, M^2, M^4, M^8, \dots]$$$ (where $$$M$$$ is the matrix we use) in $$$O(n^3 \log C)$$$ and then answer each query by $$$O(\log C)$$$ matrix-vector multiplications instead of matrix-matrix multiplications, so each query is answered in time $$$O(n^2 \log C)$$$. Note that this approach gives us the shortest path with $$$\frac{C_i}{P}$$$ edges for each last vertex in the path, we will need it later to solve the original problem.
Back to the original version: no additional constraints on $$$C_i$$$.
Let $$$F = \lfloor\frac{C_i}{P}\rfloor$$$ and $$$R = C_i \bmod P$$$. In order to obtain $$$C_i$$$ pellets, we have to traverse the whole graph $$$F$$$ times, and then collect at least $$$R$$$ pellets by traversing some of the vertices. Let's iterate on the vertex $$$v$$$ where we will end up after $$$F$$$ full traversals. Solution of Version 2 allows us to calculate the number of steps required to perform full traversals and end up in vertex $$$v$$$, so we somehow need to compute the minimum number of steps required to collect at least $$$R$$$ pellets starting from vertex $$$v$$$.
The dynamic programming used to build the auxiliary graph also calculates the minimum number of steps required to visit each subset of vertices, starting from the chosen vertex. So, for each vertex $$$v$$$ and number of steps $$$t$$$ (which is up to $$$n^2$$$), we may store the maximum number of pellets that we can collect in $$$t$$$ steps starting from $$$v$$$ — which allows us to answer each query in something like $$$O(n^3 + n^2 \log C)$$$.