풀 바꿔 심기

농부 존은 농장에 여러 종류의 풀을 심어 보고 있다. 소마다 좋아하는 풀이 다르기 때문이다. 다만 종류가 다른 풀은 서로 충분히 멀리 떨어뜨려 심어야 한다. 가까이 심으면 풀이 섞여서 되돌릴 수 없다.

존의 농장은 $N$개의 목초지로 이루어져 있고 ($1 \le N \le 200\,000$), $M$개의 목초지 쌍이 양방향 길로 이어져 있다 ($1 \le M \le 200\,000$). 이 길만 이용해서 어느 목초지에서 어느 목초지로든 갈 수 있다. 각 길의 길이는 $1$ 이상 $1\,000\,000$ 이하의 정수이고, 두 목초지를 직접 잇는 길은 많아야 하나다.

존은 각 목초지에 $K$종류의 풀 중 하나를 심는다 ($1 \le K \le N$). 시간이 지나면 어떤 목초지의 풀을 다른 종류로 바꾸기도 하는데, 이 작업을 갱신이라고 부른다. 갱신은 여러 번 일어나고, 그 효과는 모두 누적된다.

갱신을 한 번 할 때마다 존은 풀 종류가 서로 다른 두 목초지 사이의 최단 경로 길이를 알고 싶다. 즉 풀 종류가 다른 모든 목초지 쌍 중에서 가장 가까운 쌍의 거리이다. 이 값이 클수록 한 종류의 풀이 다른 종류와 섞일 걱정이 줄어든다. 어떤 갱신을 적용한 뒤에도 농장에는 풀 종류가 서로 다른 목초지가 항상 두 개 이상 있다.

입력의 30%에서는 각 목초지에 직접 연결된 길이 10개 이하이다.

첫째 줄에 네 정수 $N$, $M$, $K$, $Q$가 주어진다. $Q$는 갱신의 개수이다 ($1 \le Q \le 200\,000$).

다음 $M$개의 줄에는 길의 정보가 한 줄에 하나씩 주어진다. 각 줄은 세 정수 $A$, $B$, $L$로 이루어지며, 목초지 $A$와 목초지 $B$를 잇는 길이 $L$인 길이 있다는 뜻이다 ($1 \le A, B \le N$, $1 \le L \le 1\,000\,000$).

다음 줄에는 각 목초지에 처음 심은 풀의 종류가 목초지 $1$번부터 $N$번까지 순서대로 $N$개의 정수로 주어진다. 각 값은 $1$ 이상 $K$ 이하이다.

마지막 $Q$개의 줄에는 갱신이 한 줄에 하나씩 두 정수 $A$, $B$로 주어진다. 목초지 $A$의 풀을 종류 $B$로 바꾼다는 뜻이다 ($1 \le A \le N$, $1 \le B \le K$).

각 갱신마다 그 갱신을 적용한 뒤 풀 종류가 서로 다른 두 목초지 사이의 최단 경로 길이를 한 줄에 하나씩 출력한다.