JOI-kun 是一头生活在 IOI 森林里的野猪，森林里有 $N$ 个食物站和 $M$ 条道路。食物站编号为 $1$ 到 $N$。第 $i$ 条道路 ($1 \le i \le M$) 连接食物站 $A_i$ 和 $B_i$，双向通行，JOI-kun 走过这条路需要 $C_i$ 小时。从任意一个食物站出发，都可以通过一条或多条道路到达其他任何食物站。

JOI-kun 不擅长掉头。他不能在道路中途掉头回到他刚才所在的食物站。此外，当他通过某条道路到达一个食物站时，他不能立即沿着刚才走过的那条路返回到他刚才所在的食物站。

每天，JOI-kun 都会根据补给计划在食物站补给食物。一天的补给计划由一个包含 $L$ 个食物站的序列 $X_1, X_2, \dots, X_L$ 组成。他从食物站 $X_1$ 开始补给，按顺序访问这些食物站，最后在食物站 $X_L$ 完成补给。他可以在中途经过其他食物站。他可能会多次在同一个食物站补给，但对于每个 $j$ ($1 \le j \le L - 1$)，都有 $X_j \neq X_{j+1}$。注意，可能存在他无法执行的补给计划。

起初，JOI-kun 确定了初始补给计划 $X_1, X_2, \dots, X_L$。在第 $k$ 天的早晨 ($1 \le k \le T$)，他会将补给计划的第 $P_k$ 个值更改为 $Q_k$（即 $X_{P_k}$ 变为 $Q_k$），然后根据新的补给计划补给食物。保证在更改后，对于每个 $j$ ($1 \le j \le L - 1$)，都有 $X_j \neq X_{j+1}$。

对于这 $T$ 天的每一个补给计划，JOI-kun 都想确定他是否能够执行该补给计划，如果可以，找出执行该补给计划所需的最短时间。

任务

给定 IOI 森林的数据和 JOI-kun 的补给计划，对于 $T$ 天中的每一个补给计划，编写一个程序，确定他是否能够执行该补给计划，如果可以，找出执行该补给计划所需的最短时间。

输入格式

从标准输入读取以下数据。

• 第一行包含四个空格分隔的整数 $N, M, T$ 和 $L$。这表示 IOI 森林中有 $N$ 个食物站和 $M$ 条道路，JOI-kun 考虑 $T$ 天的补给计划，且补给计划的序列长度为 $L$。
• 接下来的 $M$ 行中，第 $i$ 行 ($1 \le i \le M$) 包含三个空格分隔的整数 $A_i, B_i$ 和 $C_i$。这表示第 $i$ 条道路连接食物站 $A_i$ 和 $B_i$，双向通行，走过需要 $C_i$ 小时。
• 接下来的 $L$ 行中，第 $j$ 行 ($1 \le j \le L$) 包含一个整数 $X_j$。这表示初始补给计划为 $X_1, X_2, \dots, X_L$。
• 接下来的 $T$ 行中，第 $k$ 行 ($1 \le k \le T$) 包含两个空格分隔的整数 $P_k$ 和 $Q_k$。这表示 JOI-kun 在第 $k$ 天的早晨将补给计划的第 $P_k$ 个值更改为 $Q_k$。

输出格式

向标准输出写入 $T$ 行。第 $k$ 行 ($1 \le k \le T$) 应包含一个整数：如果他在第 $k$ 天无法执行该补给计划，则输出 $-1$；如果可以，则输出执行该计划所需的最短时间（以小时为单位）。

数据范围

所有输入数据满足以下条件：

• $2 \le N \le 2\,000$。
• $N - 1 \le M \le 2\,000$。
• $1 \le T \le 100\,000$。
• $2 \le L \le 100\,000$。
• $1 \le A_i < B_i \le N$ ($1 \le i \le M$)。
• $(A_i, B_i) \neq (A_j, B_j)$ ($1 \le i < j \le M$)。
• 从任意一个食物站出发，都可以通过一条或多条道路到达其他任何食物站。
• $1 \le C_i \le 1\,000\,000\,000$ ($1 \le i \le M$)。
• $1 \le X_j \le N$ ($1 \le j \le L$)。
• $1 \le P_k \le L$ ($1 \le k \le T$)。
• $1 \le Q_k \le N$ ($1 \le k \le T$)。
• 对于每个 $j$ ($1 \le j \le L - 1$)，都有 $X_j \neq X_{j+1}$。在每次更改补给计划后，对于每个 $j$ ($1 \le j \le L - 1$)，也都有 $X_j \neq X_{j+1}$。

子任务

共有 4 个子任务。各子任务的分数和附加限制如下：

• 子任务 1 [12 分]：$N \le 10$，$M \le 10$，$T = 1$，$L \le 10$，$C_i \le 10$ ($1 \le i \le M$)。
• 子任务 2 [35 分]：$N \le 500$，$M \le 500$，$T = 1$。
• 子任务 3 [15 分]：$T = 1$。
• 子任务 4 [38 分]：无附加限制。

样例

样例输入 1

3 3 1 3
1 2 1
2 3 1
1 3 1
1
2
3
3 1

样例输出 1

3

样例输入 2

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

样例输出 2

5
2
3
-1

样例输入 3

5 6 1 5
1 2 8
1 3 8
1 4 8
2 5 2
3 4 6
4 5 6
2
5
1
5
3
5 2

样例输出 3

38