Switch Grass

Farmer John plants several kinds of grass on his farm, because different cows like different grass. Grass of different kinds has to be planted far enough apart. Planted close together, two kinds mix and cannot be separated again.

The farm has $N$ fields ($1 \le N \le 200\,000$), and $M$ pairs of fields are joined by two-way pathways ($1 \le M \le 200\,000$). Using only these pathways, you can walk from any field to any other field. Each pathway has an integer length between $1$ and $1\,000\,000$, and at most one pathway joins any given pair of fields.

John plants one of $K$ kinds of grass in each field ($1 \le K \le N$). Later he sometimes replaces the grass in one field with another kind. Call that an update. Several updates happen over time, and every update stays in effect.

After each update John wants the length of the shortest path between two fields whose grass kinds differ. That is, among all pairs of fields with different kinds, the distance of the closest pair. A large value means one kind is unlikely to mix with another. After every update the farm always has at least two fields with different kinds of grass.

In 30 percent of the inputs, each field is directly joined to at most 10 pathways.

The first line contains four integers $N$, $M$, $K$, and $Q$, where $Q$ is the number of updates ($1 \le Q \le 200\,000$).

Each of the next $M$ lines describes one pathway with three integers $A$, $B$, and $L$, meaning a pathway of length $L$ between field $A$ and field $B$ ($1 \le A, B \le N$, $1 \le L \le 1\,000\,000$).

The next line contains $N$ integers, the kind of grass first planted in fields $1$ through $N$ in order. Each value is between $1$ and $K$.

Each of the last $Q$ lines describes one update with two integers $A$ and $B$, meaning the grass in field $A$ becomes kind $B$ ($1 \le A \le N$, $1 \le B \le K$).

For each update, print on its own line the length of the shortest path between two fields with different kinds of grass, after the update is applied.