문제

승우는 최근 자신의 농장에서 서로 다른 종류의 소들이 서로 다른 종류의 잔디를 좋아한다는 사실을 깨닫고, 여러 종류의 잔디를 재배하는 실험을 하고 있다. 하지만 서로 다른 종류의 잔디가 뒤섞이는 것을 방지하기 위해, 종류가 다른 잔디는 충분히 멀리 떨어져 심어야 한다.

승우의 농장은 $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$)

그다음 줄에는 각 구역에 처음에 심어진 잔디의 종류를 나타내는 $N$개의 정수가 공백으로 구분되어 주어진다. (각 정수는 $1$ 이상 $K$ 이하이다.)

마지막 $Q$개의 줄에는 각 업데이트 정보를 나타내는 두 정수 $A$와 $B$가 주어진다. 이는 구역 $A$에 심어진 잔디를 $B$ 종류로 바꾼다는 의미이다.

출력

각 업데이트가 적용된 후, 서로 다른 종류의 잔디가 심어진 두 구역 사이의 최단 경로의 길이를 한 줄에 하나씩 출력한다.

예제 입력 1

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

예제 출력 1

1
3
3
1