問題文

$N$ 頂点 $M$ 辺の無向グラフがあります。 $i$ 番目の辺は頂点 $A_i$ と頂点 $B_i$ を相互に結んでいます。

頂点には色が塗られており、頂点 $i$ の色は $C_i$ です。 $1\le C_i\le 10$ が保証されます。

はじめ、すべての頂点は通行可能ではありません。

$W_i$ のコストを払うことで色 $i$ の頂点が全て通行可能になります。

独立な $Q$ 個のクエリに答えてください。 $i$ 番目のクエリは $u_i,v_i$ を用いて以下のように表されます。

• 頂点 $u_i$ と頂点 $v_i$ をつなぐパスが存在するようにコストを払うとき、払ったコストの合計としてあり得る最小値を求めてください。いくらコストを払ってもパスが存在しない場合は-1を出力してください。
  • パス上の全ての頂点(端点含む)が通行可能である必要があります。

制約

• $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$
• 入力は全て整数

入力

$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$

出力

$Q$ 行出力してください。$i$ 行目には $i$ 番目のクエリの答えを出力してください。

各クエリごとに改行してください。

サンプル

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