問題文

$N$ 個の頂点と $N-1$ 本の辺がある連結な無向グラフが与えられます。 $i$ 番目の頂点には整数 $A_i$ が書かれています。 $j$ 番目の辺は頂点 $s_i$ と頂点 $t_i$ を結んでいます。

$Q$ 個のクエリが与えられます。 $k$ 番目のクエリでは頂点 $u_k$ と頂点 $v_k$ が指定されます。 $u_k$ と $v_k$ を結ぶ最短経路上の頂点に書かれた数の総和を求めてください。

制約

• $2 \le N, Q \le 2\times10^5$
• $1 \le s_i, t_i, u_k, v_k \le N$
• $|A_i| \le 100$
• 入力は全て整数

入力

入力は以下の形式で与えられる。

出力

それぞれのクエリについて、答えを出力せよ。

入出力例1

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

7
13
5

入出力例2

4
1 -2 -8 4
1 2
4 2
2 3
2
4 1
2 3

3
-10

入出力例3

4
1 10 100 1000
1 2
2 3
3 4
4
1 3
2 4
2 3
1 4

111
1110
110
1111