Problem Statement

There is an undirected graph with $N$ vertices and $M$ edges. The $i$-th edge connects vertices $A_i$ and $B_i$ bidirectionally.

The vertices are colored, and the color of vertex $i$ is $C_i$. It is guaranteed that $1\le C_i\le 10$.

Initially, no vertex is passable.

By paying a cost of $W_i$, all vertices of color $i$ become passable.

Answer $Q$ independent queries. The $i$-th query is described using $u_i,v_i$ as follows.

• Find the minimum possible total cost paid when paying costs so that a path connecting vertex $u_i$ and vertex $v_i$ exists. If no path exists no matter how much cost is paid, output -1.
  • All vertices on the path (including the endpoints) must be passable.

Constraints

• $2 \le N \le 10^4$
• $0 \le M \le 10^4$
• $1 \le A_i ,B_i \le N$
• $1 \le C_i \le 10$
• $1 \le W_i \le 10^9 (1 \le i \le 10)$
• $1 \le Q \le 10^4$
• $1 \le u_i < v_i \le N$
• All inputs are integers.

Input

$N$ $M$
$A_1$ $B_1$
$\vdots$
$A_M$ $B_M$
$C_1$ $\ldots$ $C_N$
$W_1$ $\ldots$ $W_{10}$
$Q$
$u_1$ $v_1$
$\vdots$
$u_Q$ $v_Q$

Output

Output $Q$ lines. The $i$-th line should contain the answer to the $i$-th query.

Print a newline after each query.

Sample

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

1
3
4

2 0
1 1
1 100 100 100 100 100 100 100 100 100
1
1 2

-1

5 5
1 2
2 3
2 3
3 4
4 5
1 4 5 9 10
1000000000 1 1 1000000000 1000000000 1 1 1 1000000000 1000000000
4
1 5
2 3
1 2
1 5

5000000000
2000000000
2000000000
5000000000