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

Each node is guarded by a corrupted character (including position ) 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, Mr. Game & Watch, is located at location , and he would like to obtain Mr. Game & Watch in order to defeat the Unknown Hand.

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

#### Constraints

For all subtasks:

The graph is guaranteed to be connected.

##### Subtask 1 [10%]

##### Subtask 2 [40%]

##### Subtask 3 [50%]

No additional constraints.

#### Input Specification

The first line contains five integers , , , , and .

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

Each of the following lines contains two integers and . Each represents a bidirectional edge connecting and .

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

#### Output Specification

For each of the 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 is , go from , unlocking each character which cost

When is , go from , which requires Andy to defeat enemy at , , , , , for a total cost of

## Comments