Farmer John's Grass

Farmer John has a farm consisting of \(N\) fields and \(M\) bidirectional pathways. Each pathway has a positive integer length. Initially, each field is planted with one of \(K\) types of grass. Over time, Farmer John performs several update operations where he changes the grass type in a given field. After each update, he wishes to know the length of the shortest path between two fields that have different grass types.

Observation: In any valid path connecting two fields with different grass types, there exists at least one edge connecting two adjacent fields with different grass types. Consequently, the answer is the minimum weight among all edges whose endpoints have different grass types.

It is guaranteed that the graph is connected and that at every moment there exist at least two fields with different grass types.

Constraints:

• \(1 \leq N \leq 200{,}000\)
• \(1 \leq M \leq 200{,}000\)
• \(1 \leq K \leq N\)
• Pathway lengths are integers in the range \(1 \ldots 1{,}000{,}000\).

In some cases, each field is adjacent to at most 10 pathways.

inputFormat

The input begins with a line containing four integers \(N\), \(M\), \(Q\), and \(K\), where \(N\) is the number of fields, \(M\) is the number of pathways, \(Q\) is the number of update operations, and \(K\) is the number of grass types. The fields are numbered from 1 to \(N\).

The second line contains \(N\) integers, where the \(i\)-th integer represents the initial type of grass in field \(i\) (an integer from 1 to \(K\)).

The next \(M\) lines each contain three integers \(u\), \(v\), and \(w\) indicating that there is a bidirectional pathway between fields \(u\) and \(v\) with length \(w\). There is at most one pathway directly connecting any pair of fields.

The following \(Q\) lines each contain two integers \(x\) and \(t\), meaning that the grass type in field \(x\) is updated to type \(t\). All updates are cumulative.

outputFormat

After each update operation, output a single integer on a new line: the length of the shortest path between any two fields that have different grass types.

sample

4 4 3 3
1 1 2 3
1 2 5
2 3 3
3 4 4
1 4 10
2 2
1 3
4 1

4
4
4