题目描述

农夫约翰最近一直在在他的农场试种各种类型的草，他发现不同类型的牛，喜欢不同类型的草。 然而，他必须注意，在种草时，不同类型的草，要保持足够远的距离，以防止它们混合。

他的农场由${N（}$${1≤}$${N≤}$${200,000）}$块田地组成，其中有${M（}$${1≤}$${M≤}$${200,000）}$对田地中用小路连接。使用这些小路，可以从任何田地走到任何其他 田地。每条路的长度在${1\sim 1,000，}$${000}$范围内。 任何田地对将由顶多一条小路连接。

在每个领域，他最初都是种植${K}$柱草（${1≤}$${K≤}$${N）}$。 然而，随着时间的推移，他可能决定在某些领域将草转变为不同品种。 他称之为"更新"。 他可能会在一段时间内执行多个更新，这些都是累积的。

在每次更新之后，他想知道具有不同草品种的两个田地之间的最短路径的长度。 也就是说，在具有不同草品种的所有田地中，他想知道哪两个是最接近的。 理想情况下，这个数量很大，所以他可以防止一种品种的 草与另一品种草的混合。 保证农场将总是具有至少两个具有不同草品种的田地。

在${30\%}$的输入数据中，每个田地将连接到最多${10}$条小路。

输入格式

输入的第一行包含四个整数，${N,M,K，}$ 和${Q，}$ ${Q}$是更新次数（${1 ≤}$ ${Q ≤}$ ${200 , 000）}$。

下${M}$行描述路径；每一个包含三个整数${A,B}$和${L }$表示从字段的路径${A}$到${B（}$范围内的两个整数 ${1...N) }$长度${L}$

下一行表示每个田地中生长的草的初始类型（${N}$范围内的整数${1...K）}$。最后，最后问每行描述一次更新，由两个整数指定${A}$和${B, }$田野里的草一个将被更新为类型${B}$。

输出格式

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

样例

输入样例

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