캣맘

최근 캣맘은 자신의 고양이들에게 다양한 종류의 사료를 제공하려고 실험을 하고있습니다. 이는 다른 종류의 고양이들이 다른 종류의 사료를 선호한다는 것을 깨달았기 때문입니다. 그러나, 그녀는 다른 종류의 사료들가 서로 섞이지 않게 주의해야합니다.

주택가는 $N$개의 필드로 구성되어 있으며, 이 필드들은 양방향 길로 연결되어 있습니다 ($1 \leq N \leq 200,000$). 이 경로를 사용하여, 어느 필드에서라도 다른 필드로 걸어갈 수 있습니다. 각 길은 범위 $1 \ldots 1,000,000$의 정수 길이를 가집니다. 필드 쌍 중 어느 것도 직접 길로 연결되어있는 경우는 최대 한 번입니다.

각 필드에서 캣맘은 처음에 $K$ 종류의 사료 중 하나를 놓습니다 ($1 \leq K \leq N$). 그러나 시간이 지나면, 그녀는 어떤 필드의 사료를 다른 종류로 바꾸기로 결정할 수 있습니다. 그녀는 이것을 '업데이트' 작업이라고 부릅니다. 그녀는 시간이 지남에 따라 여러 업데이트를 수행할 수 있으며, 이들은 모두 누적됩니다.

각 업데이트 이후에, 캣맘은 서로 다른 사료 종류의 두 필드 사이의 최단 경로 길이를 알고 싶어합니다. 즉, 모든 필드 쌍 중 서로 다른 종류의 사료를 가진 두 필드를 선택하고, 가장 가까운 거리를 알고 싶습니다. 이 상태는 이상적으로 숫자가 크므로, 한 종류의 사료가 다른 종류의 사료와 섞이는 것을 막을 수 있습니다. 주택가에는 항상 적어도 두 종류의 사료가 있음이 보장됩니다.

입력 케이스의 30퍼센트에서 각 필드는 최대 10개의 길로 직접 연결됩니다.

첫 번째 입력 라인에는 네 개의 정수 $N$, $M$, $K$, $Q$가 존재하며, 이때 $Q$는 업데이트 수입니다 ($1 \leq Q \leq 200,000$). 다음 $M$개의 라인들은 경로를 설명하며, 각각은 필드 $A$에서 필드 $B$로의 길을 나타내는 세 개의 정수 $A$, $B$, $L$을 포함합니다 (둘 다 범위 $1 \ldots N$의 정수). 다음 라인은 각 필드에서 놓인 초기 사료 종류를 나타냅니다 ($N$개의 범위 $1 \ldots K$의 정수). 마지막으로, 마지막 $Q$개의 라인 각각은 필드 $A$의 사료가 종류 $B$로 업데이트되예정임을 두 개의 정수 $A$, $B$로 이루어진 업데이트를 설명합니다.

각 업데이트에 대해, 업데이트가 적용된 후 서로 다른 사료 종류의 두 필드 사이의 최단 경로 길이를 출력하세요.