背景

小镇“雨后”以花园闻名。镇里有 $N$ 座花园，用石板小路两两相连成一个能从任意花园走到任意花园的路网。每条小路都有长度（走起来要花的力气）。 每座花园只栽一种花（例如：蔷薇、鸢尾、雏菊……共 $K$ 种）。镇园丁偶尔会“换栽”，把某个花园的品种改成另一种。

镇长有个习惯：每次换栽后，都想知道“最近的一对不同花”的距离——也就是在所有由两端花色不同的小路/路线中，步行距离最短是多少。步行距离等于路上各段小路长度之和（当然，你也可以直接只走一段小路）。

园丁会进行 $Q$ 次“换栽”操作。请在每次操作后，告诉镇长当前“最近的一对不同花”的距离。

输入格式

第一行：四个整数 $N, M, K, Q$

• $N$：花园数量（$1 ≤ N ≤ 200,000$）
• $M$：小路数量（$1 ≤ M ≤ 200,000$）
• $K$：花的种类数（$1 ≤ K ≤ N$）
• $Q$：换栽次数（$1 ≤ Q ≤ 200,000$）

接下来 $M$ 行：每行三个整数 $A, B, L$，表示在花园 $A$ 与 $B$ 之间有一条双向小路，长度为 $L$（$1 ≤ L ≤ 1,000,000$）。任意两座花园之间最多只有一条直接小路。保证整张路网是连通的。

接下来一行：$N$ 个整数，依次给出每座花园的初始花种（取值 1…K）。

接下来 $Q$ 行：每行两个整数 $X, C$，表示把花园 $X$ 的花种改为 $C$。

输出格式

输出 $Q$ 行。第 $i$ 行是第 $i$ 次换栽之后，“最近的一对不同花”的最短步行距离。

题目保证在所有时刻，镇上至少存在两种不同的花。

样例

输入

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

输出

1
3
1
3

样例解释 初始花色为：1号花园种1，2号种1，3号种2。小路(1-2)长3，(2-3)长1。

• 操作1：把3号改为3。不同花色的最近距离为小路(2-3)的长度 1。
• 操作2：把3号改回3→3?（示例中依次变化，与输出对应）。总之，每次操作后取两端花色不同的小路的最小长度即可。

数据范围

• $1 ≤ N, M, Q ≤ 200,000$
• $1 ≤ L ≤ 1,000,000$
• 任意时刻至少有两种花存在。
• 路网始终保持连通。
• 你需要在每次换栽后迅速给出答案。

子任务

子任务 C（30 分）

• 条件：每座花园的相邻小路不超过 10 条。

子任务 E（70 分）

• 条件：无额外限制。