题目描述

原题来自 USACO 2017 US Open Contest, Platinum Problem 2. Switch Grass，数据范围有改动。

「这场圣杯战争……从一开始，就很不对劲。」

由于这场圣杯战争过于异常，作为中立调停的「裁定者」贞德被大圣杯召唤。

圣杯战争在 $n$ 座城市内进行，这些城市之间通过 $m$ 条路径相互连接彼此可以相互到达，由于某些特殊规则，所有的从者只能通过这 $m$ 条路径从一个城市到达另一个城市。开始时，每个城市都会出现有且仅有一位从者。

令贞德不安的是，从者们既不是各自为战，也没有完整的阵营组合：每位从者分属一个阵营 $k_i$，相同阵营的从者之间不会相互攻击，并且所有阵营均没有固定的从者数目。

在混战中，被击杀的从者会直接回归英灵座而消失，退出这场圣杯战争。大圣杯继续召唤一位英灵作为从者，让他/她降临在被击杀的从者所在的城市。

陷入迷惘的贞德整理了思绪，决定先去监督不同阵营的从者之间相距最近的一组战斗（指两个从者到达对方城市的最短距离），并希望知道每次更换（接着上一次的更新进行）了从者后所有战斗的最短距离。请帮助贞德完成这个任务。

大圣杯保证不会只剩下一种阵营。

输入格式

第一行，包含四个整数 $n,m,K,Q$，分别表示城市个数，路径条数，本次圣杯战争参战的不同阵营数目，以及更换从者的次数。

接下来 $m$ 行，每行包含三个整数 $u,v,w$，表示城市 $u,v$ 之间存在一条长度为 $w$ 的路径。

接下来一行，包含 $n$ 个整数 $k_1,k_2,\cdots ,k_n$，表示开始时每个城市召唤的从者所属阵营。

接下来 $Q$ 行，每行包含两个整数 $x,k$，表示城市 $x$ 重新召唤了所属阵营为 $k$ 的从者。

输出格式

对于每一次从者更换，输出一行包含一个整数，表示不同阵营之间战斗的最短距离。

样例

input

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

output

1
3
3
1

数据范围与提示

对于 $20\%$ 的数据，$1\le n,m\le 10^3,1\le K\le 10^3,1\le Q\le 100$；

对于 $40\%$ 的数据，$1\le n\le 5\times 10^3,1\le m\le 10^4,1\le K\le 10^6,1\le Q\le 10^4$；

对于 $60\%$ 的数据，$1\le n\le 2\times 10^4,1\le m\le 4\times 10^4,1\le K\le 10^6,1\le Q\le 10^4$；

对于 $100\%$ 的数据，$1\le u,v,x\le n\le 2\times 10^5,1\le m\le 4\times 10^5,1\le k\le K\le 10^6,1\le Q\le 2\times 10^5,1\le w\le 10^6$。

最后四组数据中保证存在一组数据，每座城市最多只有 $10$ 条路径连向其他城市。

当前的更改是在完成前面所有更改的前提下继续的。