Farmer John 最近一直在尝试在他的农场里种植不同种类的牧草，因为他意识到不同种类的奶牛喜欢不同种类的牧草。然而，他必须小心，确保不同种类的牧草种植得足够远，以防止它们混在一起。

FJ 的农场由 $N$ 个田地组成（$1 \leq N \leq 200,000$），其中有 $M$ 对田地通过双向路径相连（$1 \leq M \leq 200,000$）。通过这些路径，可以从任意一个田地走到另一个田地。每条路径的长度为 $1 \ldots 1,000,000$ 之间的整数。任意一对田地之间最多只有一条直接路径。

在每个田地中，FJ 最初种植了 $K$ 种牧草中的一种（$1 \leq K \leq N$）。然而，随着时间的推移，他可能会决定将某个田地的牧草更换为另一种类型。他称之为“更新”操作。他可能会在一段时间内执行多次更新，这些更新都是累积的。

每次更新后，FJ 都想知道两个具有不同牧草类型的田地之间的最短路径长度。也就是说，在所有具有不同牧草类型的田地对中，他想知道哪一对距离最近。理想情况下，这个数字越大越好，这样他就可以防止一种类型的牧草与另一种类型的牧草混合。保证农场中始终至少有两个田地具有不同的牧草类型。

在 30% 的输入用例中，每个田地最多直接连接 10 条路径。

输入格式

第一行包含四个整数 $N$、$M$、$K$ 和 $Q$，其中 $Q$ 是更新次数（$1 \leq Q \leq 200,000$）。接下来的 $M$ 行描述路径；每行包含三个整数 $A$、$B$ 和 $L$，表示从田地 $A$ 到田地 $B$（均为 $1 \ldots N$ 范围内的整数）有一条长度为 $L$ 的路径。下一行表示每个田地最初种植的牧草类型（$N$ 个 $1 \ldots K$ 范围内的整数）。最后，$Q$ 行每行描述一个更新，由两个整数 $A$ 和 $B$ 指定，表示田地 $A$ 的牧草更新为类型 $B$。

输出格式

对于每次更新，在应用更新后，打印两个具有不同牧草类型的田地之间的最短路径长度。

样例

样例输入 1

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

样例输出 1

1
3
3
1