JOI-kun là một chú lợn rừng sống trong khu rừng IOI. Khu rừng có \(N\) trạm thức ăn, được đánh số từ \(1\) đến \(N\), và \(M\) con đường. Con đường thứ \(i\) nối hai trạm \(A_i\) và \(B_i\) theo cả hai chiều; đi hết con đường theo một trong hai chiều đều mất \(C_i\) giờ. Có thể đi từ bất kỳ trạm nào đến bất kỳ trạm nào khác bằng các con đường.

JOI-kun không giỏi quay đầu. Cậu không thể quay đầu giữa một con đường để trở về trạm vừa rời đi. Hơn nữa, khi vừa đến một trạm bằng một con đường, cậu không thể lập tức đi ngược lại trên chính con đường đó để trở về trạm trước đó.

Mỗi ngày, JOI-kun tiếp tế thức ăn theo một kế hoạch gồm dãy \(L\) trạm \(X_1,X_2,\ldots,X_L\). Cậu bắt đầu tiếp tế tại trạm \(X_1\), đến các trạm trong kế hoạch theo đúng thứ tự và kết thúc việc tiếp tế tại \(X_L\). Giữa hai lần tiếp tế, cậu được phép đi qua các trạm khác. Một trạm có thể xuất hiện nhiều lần trong kế hoạch, nhưng \(X_j \ne X_{j+1}\) với mọi \(1 \le j < L\). Có thể có những kế hoạch mà cậu không thực hiện được.

Ban đầu, JOI-kun chọn kế hoạch \(X_1,X_2,\ldots,X_L\). Vào sáng ngày thứ \(k\) trong \(T\) ngày, cậu thay phần tử thứ \(P_k\) của kế hoạch bằng \(Q_k\), tức là gán \(X_{P_k}=Q_k\), rồi thực hiện kế hoạch sau khi thay đổi. Các thay đổi được giữ lại cho những ngày tiếp theo. Đảm bảo rằng sau mỗi thay đổi, hai phần tử liên tiếp của kế hoạch vẫn khác nhau.

Với mỗi ngày, hãy xác định JOI-kun có thể thực hiện kế hoạch hay không. Nếu có, hãy tính thời gian ít nhất cần thiết để hoàn thành kế hoạch đó.

Dữ liệu vào

• Dòng đầu chứa bốn số nguyên \(N,M,T,L\): số trạm, số đường, số ngày và độ dài kế hoạch.
• Trong \(M\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên \(A_i,B_i,C_i\). Con đường thứ \(i\) nối \(A_i\) với \(B_i\) theo cả hai chiều và mất \(C_i\) giờ để đi hết.
• Trong \(L\) dòng tiếp theo, dòng thứ \(j\) chứa số nguyên \(X_j\), mô tả kế hoạch ban đầu.
• Trong \(T\) dòng tiếp theo, dòng thứ \(k\) chứa hai số nguyên \(P_k,Q_k\), mô tả phép thay đổi \(X_{P_k}=Q_k\) vào sáng ngày thứ \(k\).

Các số trên cùng một dòng được phân cách bằng dấu cách.

Dữ liệu ra

In \(T\) dòng. Dòng thứ \(k\) chứa \(-1\) nếu không thể thực hiện kế hoạch của ngày thứ \(k\); ngược lại, in thời gian ít nhất, tính bằng giờ, để thực hiện kế hoạch đó.

Ràng buộc

• \(2 \le N \le 2000\).
• \(N-1 \le M \le 2000\).
• \(1 \le T \le 100\,000\).
• \(2 \le L \le 100\,000\).
• \(1 \le A_i < B_i \le N\) với \(1 \le i \le M\).
• \((A_i,B_i) \ne (A_j,B_j)\) với \(1 \le i < j \le M\).
• Có thể đi từ bất kỳ trạm nào đến bất kỳ trạm nào khác bằng các con đường.
• \(1 \le C_i \le 1\,000\,000\,000\) với \(1 \le i \le M\).
• \(1 \le X_j \le N\) với \(1 \le j \le L\).
• \(1 \le P_k \le L\) và \(1 \le Q_k \le N\) với \(1 \le k \le T\).
• \(X_j \ne X_{j+1}\) với \(1 \le j < L\), cả trong kế hoạch ban đầu lẫn sau mỗi thay đổi.

Phân nhóm

1. \(12\) điểm: \(N \le 10\), \(M \le 10\), \(T=1\), \(L \le 10\) và \(C_i \le 10\) với mọi \(1 \le i \le M\).
2. \(35\) điểm: \(N \le 500\), \(M \le 500\), \(T=1\).
3. \(15\) điểm: \(T=1\).
4. \(38\) điểm: Không có ràng buộc bổ sung.

Ví dụ

3 3 1 3
1 2 1
2 3 1
1 3 1
1
2
3
3 1

3

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

5
2
3
-1

5 6 1 5
1 2 8
1 3 8
1 4 8
2 5 2
3 4 6
4 5 6
2
5
1
5
3
5 2

38

Nguồn

JOI 2018, trại huấn luyện mùa xuân, ngày thi 4: Wild Boar.