Andy just started the story mode for Super Smash Bros – World of Light. World of Light consists of ~N~ nodes and ~M~ edges connecting the ~N~ nodes. Unknown Hand is at location ~Y~, and Andy starts at location ~X~.

Each node is guarded by a corrupted character (including position ~X~) and takes a certain amount of time to defeat. After the corrupted character is defeated, you can go through the node and adjacent edges as many times as you want without any cost in time. Andy's favourite character, Lucina, is located at location ~A~, and he would like to obtain Lucina in order to defeat the Unknown Hand.

Andy obtains Lucina if he reaches node ~A~. However, he can't tell where node ~A~ is, so he asks you to answer ~Q~ queries to determine the minimum amount of time he needs to beat the game if a location given is location ~A~.

Constraints

For all subtasks:

~1 \le X, Y, u_i, v_i \le N \le 10^5~

~1 \le M, Q \le 2 \times 10^5~

~1 \le a_i \le 10^9~

The graph is guaranteed to be connected.

Subtask 1 [10%]

~Q = 1~

~A = X~

Subtask 2 [40%]

~1 \le N \le 1\,000~

~1 \le M, Q \le 2\,000~

Subtask 3 [50%]

No additional constraints.

Input Specification

The first line contains five integers ~N~, ~M~, ~X~, ~Y~, and ~Q~.

The next line contains an array ~a~ of ~N~ integers with the ~i~th integer representing the time it takes to beat the corrupted character at node ~i~.

Each of the following ~M~ lines contains two integers ~u_i~ and ~v_i~. Each represents a bidirectional edge connecting ~u_i~ and ~v_i~.

The last ~Q~ lines contain one integer ~A~, asking for the minimum time to go from node ~X~ to node ~Y~ while passing by node ~A~.

Output Specification

For each of the ~Q~ queries, output each answer on one line.

Sample Input

7 8 1 7 7
2 3 7 6 4 3 5
1 2
2 5
4 5
5 3
5 6
3 6
6 7
5 7
1
2
3
4
5
6
7

Sample Output

14
14
21
20
14
17
14

Sample Explanation

When ~A~ is ~1~, go from ~1 \to 2 \to 5 \to 7~, which costs ~2+3+4+5 = 14~.

When ~A~ is ~4~, go from ~1 \to 2 \to 5 \to 4 \to 5 \to 7~, which requires Andy to defeat the enemies at ~1~, ~2~, ~4~, ~5~, ~7~, for a total cost of ~2+3+6+4+5 = 20~.