地震学者の予測によると、Bitland で強い地震が起こると考えられています。Bitland には $1$ から $n$ まで番号の付いた $n$ 個の都市があり、その一部は双方向の道路で結ばれています。経路とは、隣り合う各 2 都市が道路で結ばれている都市の列です。経路の長さは、その経路に含まれるすべての道路の長さの和です。都市の組 $(a,b)$ の間の最短経路とは、都市 $a$ から始まり都市 $b$ で終わる経路のうち、長さが最小のものです。

政府が最も問題視しているのは原子力発電所（NPP）からの放射線漏れです。これが起きた場合、住民を避難させる必要があります。各原子力発電所は都市のいずれかにあり、全部で $k$ か所あります。各都市に原子力発電所は高々 1 か所です。政府は地震の際に機能する避難計画を作成したいと考えています。

都市間の避難経路は、原子力発電所があるすべての都市からできるだけ遠くなるように選ばなければなりません。経路の危険度は、経路上の都市と原子力発電所がある都市との距離の最小値で評価します。より厳密には、経路上の都市を $(a_1,a_2,\ldots,a_s)$、原子力発電所がある都市を $(g_1,g_2,\ldots,g_k)$ とすると、経路の危険度は、すべての $\operatorname{dist}(a_i,g_j)$ の最小値です。ここで $\operatorname{dist}(a,b)$ は $a$ と $b$ の間の最短経路の長さです。

都市の組 $(s_i,t_i)$ が $Q$ 組与えられます。それぞれについて、危険度が最大となる避難計画を求めてください。

入力

最初の行には、Bitland の都市数と道路数を表す 2 整数 $n,m$ が空白区切りで与えられます（$2\le n\le10^5$, $1\le m\le5\cdot10^5$）。続く $m$ 行には、各行に 1 本ずつ道路の情報が与えられます。各道路は 3 数 $a_i,b_i,w_i$（$1\le a_i,b_i\le n$, $1\le w_i\le1000$, $a_i\ne b_i$）で表され、接続する都市の組と道路の長さを示します。次の行には原子力発電所がある都市数を表す整数 $k$（$1\le k\le n$）が与えられます。次の行には $k$ 個の整数 $g_i$（$1\le g_i\le n$, $1\le i\le k$）が与えられ、原子力発電所がある都市の番号を示します。次の行には、避難計画を求める都市の組の数 $Q$（$1\le Q\le10^5$）が与えられます。続く $Q$ 行のそれぞれに、$i$ 番目の都市の組 $(s_i,t_i)$（$1\le s_i,t_i\le n$, $s_i\ne t_i$）が与えられます。

自分自身を結ぶ道路はなく、どの 2 都市間にも道路は高々 1 本であり、任意の都市から任意の都市へ到達できることが保証されます。

出力

$Q$ 行出力してください。

$i$ 行目に、都市の組 $(s_i,t_i)$ に対する危険度の最大値を表す整数を 1 つ出力してください。

小課題

この問題には 5 つの小課題があります。

1. $n\le10^3$, $1\le m\le10^3$, $Q\le10^3$。$Q$ 組の各 $(s_i,t_i)$ の間には直接結ぶ道路があります。10 点。
2. $n\le10^5$, $Q\le10^5$。$Q$ 組の各 $(s_i,t_i)$ の間には直接結ぶ道路があります。13 点。
3. $n\le15$, $1\le m\le200$, $1\le Q\le200$。12 点。
4. $Q=1$。19 点。
5. 上記の問題文の制約に従います。46 点。

入出力例

入力 1

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

出力 1

5
5
0
7
8

注記