根据地震学家的预测，Bitland 即将发生强震。Bitland 有 $n$ 座城市，编号从 $1$ 到 $n$。其中一些城市之间由双向道路连接。我们将路径视为一系列城市，其中每相邻的两座城市都由某条道路连接。路径的长度定义为该路径所涉及的所有道路长度之和。两座城市 $(a, b)$ 之间的最短路径定义为从城市 $a$ 出发到达城市 $b$ 的长度最小的路径。

该国政府认为核电站（NPP）的辐射泄漏是主要问题——在这种情况下，将需要疏散人口。每座核电站都位于其中一座城市中，核电站总数为 $k$，每座城市最多只有一座核电站。政府希望制定一个在地震期间有效的疏散计划。

必须选择城市之间的疏散路径，使其尽可能远离所有设有核电站的城市。路径的危险程度通过计算该路径上的城市与任何设有核电站的城市之间的最小距离来估算。更正式地说，设 $(a_1, a_2, \dots, a_s)$ 为路径上的城市，设 $(g_1, g_2, \dots, g_k)$ 为设有核电站的城市，则该路径的危险程度等于所有 $dist(a_i, g_j)$ 中的最小值，其中 $dist(a, b)$ 等于城市 $a$ 和 $b$ 之间的最短路径长度。

给定 $Q$ 对城市 $(s_i, t_i)$，对于每一对城市，你需要制定一个具有最大危险程度的疏散计划。

输入格式

第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 10^5, 1 \le m \le 5 \cdot 10^5$），分别表示 Bitland 的城市数量和道路数量。接下来的 $m$ 行，每行描述一条道路。每条道路由三个数字 $a_i, b_i, w_i$（$1 \le a_i, b_i \le n, 1 \le w_i \le 1000, a_i \neq 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 \le 10^5$），表示疏散计划的城市对数量。接下来的 $Q$ 行，每行给出第 $i$ 对城市 $(s_i, t_i)$（$1 \le s_i, t_i \le n, s_i \neq t_i$）。

保证没有道路连接城市自身，任意两座城市之间不超过一条道路，且任意两座城市之间均可达。

输出格式

输出 $Q$ 行。 第 $i$ 行输出一个整数，表示城市对 $(s_i, t_i)$ 的最大危险程度。

子任务

本任务包含五个子任务：

1. $n \le 10^3, 1 \le m \le 10^3, Q \le 10^3$。每对 $(s_i, t_i)$ 之间存在直接道路。分值 10 分。
2. $n \le 10^5, Q \le 10^5$。每对 $(s_i, t_i)$ 之间存在直接道路。分值 13 分。
3. $n \le 15, 1 \le m \le 200, 1 \le Q \le 200$。分值 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

说明