题目描述

给定一张 $n$ 点 $m$ 边的无向图，其中有 $k$ 个点上有特殊标记。你需要回答 $q$ 次询问，每次询问包含两个整数 $s_i$ 和 $t_i$，请求出从 $s_i$ 到 $t_i$ 的路径中，在尽可能远离有标记的点的情况下距离有标记的点的长度的最小值。

输入格式

第一行：四个整数 $n,m,k,q$，意义如题；

接下来 $m$ 行，每行三个整数 $a_i,b_i,l_i$，表示存在一条连接 $a_i$ 和 $b_i$ 的，长度为 $l_i$ 的边；

接下来 $k$ 行，每行一个整数 $f_i$，表示第 $f_i$ 个点有标记；

接下来 $q$ 行，每行两个正整数 $s_i,t_i$，意义如题。

输出格式

输出 $q$ 行，每行一个整数，表示从 $s_i$ 到 $t_i$ 的路径中到有标记的点的距离最大的路径到有标记的点的距离。

输入输出样例

输入 #1

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

输出 #1

7
5
0

输入 #2

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

输出 #2

8
8
11
0
6

说明/提示

样例 #1 解释

$6$ 个点 $6$ 条边，第 $1,6$ 个点做了标记。

从点 $3$ 到点 $4$ 的路径有3 2 4和3 5 4两条。前者的最短距离为 $5$，后者为 $7$，所以输出 $7$。

从点 $5$ 到点 $2$ 的路径中，点 $2$ 一定是距离标记点最近的点，所以输出 $5$。

从点 $1$ 到点 $4$ 的路径中，由于点 $1$ 被标记，所以输出 $0$。

样例 #2 解释

（详细解释无，有需要者可以自行打开 PPT 看本样例的图）

数据规模与约定

• $2 \le n \le 10^5$，$1 \le m \le 2 \times 10^5$，$1 \le k \le n$，$1 \le q \le 10^5$，$1 \le l_i \le 1000$；
• $1 \le a_i,b_i,f_i,s_i,t_i \le n$，给出的图无重边，无自环，保证图联通；
• 对于任意一组 $(s_i,t_i)$，保证 $s_i\neq t_i$。