Switch Grass

Có $N$ cánh đồng và $M$ con đường hai chiều. Mỗi cánh đồng trồng một trong $K$ loại cỏ. Đôi khi Farmer John quyết định thay đổi loại cỏ của một cánh đồng. Sau mỗi thay đổi, hãy tìm khoảng cách ngắn nhất giữa hai cánh đồng có loại cỏ khác nhau.

Khoảng cách giữa hai cánh đồng là độ dài đường đi ngắn nhất nối chúng.

Dữ liệu vào

Dòng đầu chứa bốn số nguyên $N$, $M$, $K$, $Q$.

• $M$ dòng tiếp theo, mỗi dòng ba số nguyên $A$, $B$, $L$: con đường hai chiều giữa cánh đồng $A$ và $B$ với độ dài $L$.

Dòng tiếp theo chứa $N$ số nguyên: loại cỏ ban đầu của mỗi cánh đồng (từ $1$ đến $K$).

• $Q$ dòng tiếp theo, mỗi dòng hai số nguyên $A$, $B$: thay đổi loại cỏ cánh đồng $A$ thành loại $B$.

Dữ liệu ra

In $Q$ dòng, dòng thứ $i$ là khoảng cách ngắn nhất giữa hai cánh đồng có loại cỏ khác nhau sau lần cập nhật thứ $i$.

Ràng buộc

• $1\le N,M,K,Q\le 2\times {10}^5$
• $1\le L\le {10}^6$
• Đồ thị liên thông: luôn có đường đi giữa hai cánh đồng bất kỳ
• Luôn tồn tại ít nhất hai cánh đồng có loại cỏ khác nhau (kể cả sau mỗi lần cập nhật)
• Không có hai con đường cùng nối một cặp cánh đồng
• 30% test: mỗi cánh đồng có bậc không quá 10

Ví dụ