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

The first line contains four integers n, m, q and s (2 ≤ n ≤ 15; n ≤ m ≤ n(n-1); 1 ≤ q ≤ 5000; 1 ≤ s ≤ 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 ≤ a_i ≤ 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 ≤ v_i, u_i ≤ n; v_i ≠ 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 ≤ C_i ≤ 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).

Examples

Input


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


Output


1
3


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


Output


2
6
10
13


Input


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


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) → 3(+2) → 4(+2). In such a way 7 pellets were collected.

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

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

Difficulty: VERY_HARD
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions: