#P1346I. Pac-Man 2.0

Pac-Man 2.0

Description

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 nn safe zones with mm 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 ss.

All pellets are scattered over the safe zones; initially, the ii-th safe zone contains aia_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 (aia_i new pellets spawn in the ii-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 qq goals in the game, the ii-th goal is to collect at least CiC_i pellets from the beginning of the game. Polycarp denotes the difficulty of the ii-th goal as the minimum number of times the player has to traverse a one-directional pathway in order to collect CiC_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!

The first line contains four integers nn, mm, qq and ss (2n152 \le n \le 15; nmn(n1)n \le m \le n(n-1); 1q50001 \le q \le 5000; 1sn1 \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 nn integers a1a_1, a2a_2, ..., ana_n (1ai1091 \le a_i \le 10^9), where aia_i is the initial number of pellets in the ii-th safe zone (and the number of pellets that spawn in the ii-th safe zone when the last pellet in the world is collected).

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

The last line contains qq integers C1C_1, C2C_2, ..., CqC_q (1Ci10151 \le C_i \le 10^{15}), where CiC_i is the minimum number of pellets the player has to collect in order to fulfil the ii-th goal.

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

Input

The first line contains four integers nn, mm, qq and ss (2n152 \le n \le 15; nmn(n1)n \le m \le n(n-1); 1q50001 \le q \le 5000; 1sn1 \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 nn integers a1a_1, a2a_2, ..., ana_n (1ai1091 \le a_i \le 10^9), where aia_i is the initial number of pellets in the ii-th safe zone (and the number of pellets that spawn in the ii-th safe zone when the last pellet in the world is collected).

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

The last line contains qq integers C1C_1, C2C_2, ..., CqC_q (1Ci10151 \le C_i \le 10^{15}), where CiC_i is the minimum number of pellets the player has to collect in order to fulfil the ii-th goal.

Output

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

Samples

样例输入 1

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

样例输出 1

1
3

样例输入 2

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

2
6
10
13

样例输入 3

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

样例输出 3

3
13
401

Note

Consider the first test. In order to collect 55 pellets, the player should collect 33 pellets in the safe zone 11 (which is starting), move to zone 33, collect 22 pellets there.

In order to collect 88 pellets, the player should collect 33 pellets in the safe zone 11, go to 22, collect 11 pellet, go to 11 without getting pellets, go to 33, collect 22 pellets. Now the last pellet in the world is collected, so they are respawned. The player can collect 22 pellets in the safe zone 33 and now the number of collected pellets is 88.

Consider the second test.

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

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

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