题目描述

给定一个 $n$ 个点，$m$ 条边的无向连通图，图有边权，每个点有一个颜色，颜色总数为 $c$。

有 $q$ 次操作，每次操作改变某一个点的颜色，每次操作后求图中不同颜色点的最短距离。

输入格式

从 color.in 读入。

第一行为四个正整数 $n,m,c,q$。

接下来 $m$ 行每行三个正整数 $u,v,w$，表示有一条连接 $u$ 和 $w$ 且边权为 $w$ 的边。

接下来一行 $n$ 个正整数表示每个点的初始颜色。

接下来 $q$ 行每行两个正整数 $x,y$ ，表示将 $x$ 点的颜色修改为 $y$。

输出格式

输出到 color.out 中。

对于 $q$ 次操作，每次操作输出图中不同颜色点的最短距离。

样例

样例 1

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

1
3
3
1

样例 2

见附加文件中 color2.in 与 color2.out。

数据范围

• 对于 $20\%$ 的数据，$n,m,q\le 3\times 10^3$。
• 对于 $50\%$ 的数据，$n,q\le 5\times 10^4$。
• 对于 $100\%$ 的数据，$1\le n\le 2\times 10^5$，$n-1\le m\le \min(\frac{n\times (n-1)}{2},3\times 10^5)$，颜色数 $c\le n$，$1\le q\le 2\times 10^5$，$0\le w\le 10^6$，保证任意时刻图中颜色至少存在两种。