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

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

Mỗi ngày, JOI-kun tiếp tế thức ăn tại các trạm theo một kế hoạch tiếp tế. Kế hoạch của một ngày gồm một dãy $L$ trạm thức ăn $X_1,X_2,\ldots,X_L$. Chú bắt đầu tiếp tế tại trạm $X_1$, ghé thăm các trạm theo thứ tự này và kết thúc tiếp tế tại trạm $X_L$. Chú được phép đi qua các trạm thức ăn khác trên đường. Một trạm có thể được tiếp tế nhiều lần, nhưng $X_j \ne X_{j+1}$ với mọi $j$ ($1 \le j \le L-1$). Lưu ý rằng có thể có kế hoạch tiếp tế mà chú không thể thực hiện.

Ban đầu, JOI-kun xác định kế hoạch tiếp tế $X_1,X_2,\ldots,X_L$. Vào buổi sáng ngày thứ $k$ ($1 \le k \le T$), chú thay giá trị thứ $P_k$ trong kế hoạch bằng $Q_k$ (tức là $X_{P_k}$ trở thành $Q_k$), rồi tiếp tế theo kế hoạch mới. Đảm bảo rằng sau mỗi lần thay đổi, $X_j \ne X_{j+1}$ với mọi $j$ ($1 \le j \le L-1$).

Với mỗi kế hoạch trong $T$ ngày, JOI-kun muốn biết có thể thực hiện kế hoạch đó hay không và nếu có thì thời gian ít nhất để tiếp tế theo kế hoạch đó là bao nhiêu.

Yêu cầu

Cho dữ liệu về khu rừng IOI và các kế hoạch tiếp tế của JOI-kun, hãy viết chương trình xác định, với mỗi kế hoạch trong $T$ ngày, liệu chú có thể thực hiện kế hoạch hay không và nếu có thì tìm thời gian ít nhất để tiếp tế theo kế hoạch đó.

Dữ liệu vào

Đọc dữ liệu sau từ đầu vào chuẩn.

• Dòng đầu tiên chứa bốn số nguyên $N$, $M$, $T$ và $L$ cách nhau bởi dấu cách. Điều này có nghĩa là khu rừng IOI có $N$ trạm thức ăn và $M$ con đường, JOI-kun xem xét kế hoạch tiếp tế cho $T$ ngày và mỗi kế hoạch là một dãy có độ dài $L$.
• Dòng thứ $i$ ($1 \le i \le M$) trong $M$ dòng tiếp theo chứa ba số nguyên $A_i$, $B_i$ và $C_i$ cách nhau bởi dấu cách. Con đường thứ $i$ nối hai trạm $A_i$ và $B_i$ theo cả hai chiều và JOI-kun mất $C_i$ giờ để đi hết con đường theo một trong hai chiều.
• Dòng thứ $j$ ($1 \le j \le L$) trong $L$ dòng tiếp theo chứa một số nguyên $X_j$. Kế hoạch tiếp tế ban đầu là $X_1,X_2,\ldots,X_L$.
• Dòng thứ $k$ ($1 \le k \le T$) trong $T$ dòng tiếp theo chứa hai số nguyên $P_k$ và $Q_k$ cách nhau bởi dấu cách. JOI-kun sẽ thay giá trị thứ $P_k$ trong kế hoạch bằng $Q_k$ vào buổi sáng ngày thứ $k$.

Dữ liệu ra

In $T$ dòng ra đầu ra chuẩn. Dòng thứ $k$ ($1 \le k \le T$) chứa -1 nếu chú không thể thực hiện kế hoạch của ngày thứ $k$, hoặc thời gian ít nhất tính bằng giờ để thực hiện kế hoạch đó nếu có thể.

Giới hạn

Tất cả dữ liệu vào thỏa mãn các điều kiện sau.

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

Nhiệm vụ con

Có 4 nhiệm vụ con. Điểm số và các giới hạn bổ sung của từng nhiệm vụ con như sau:

Nhiệm vụ con 1 [12 điểm]

• $N \le 10$.
• $M \le 10$.
• $T=1$.
• $L \le 10$.
• $C_i \le 10$ ($1 \le i \le M$).

Nhiệm vụ con 2 [35 điểm]

• $N \le 500$.
• $M \le 500$.
• $T=1$.

Nhiệm vụ con 3 [15 điểm]

• $T=1$.

Nhiệm vụ con 4 [38 điểm]

Không có giới hạn bổ sung.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

3

Ghi chú

Trong ví dụ 1, kế hoạch ban đầu là $1,2,3$. Vào buổi sáng ngày thứ nhất, JOI-kun thay giá trị thứ ba của kế hoạch bằng $1$. Vì thế, kế hoạch của ngày thứ nhất là $1,2,1$.

Đầu tiên, JOI-kun tiếp tế tại trạm $1$. Sau đó, chú dùng con đường thứ nhất đi từ trạm $1$ đến trạm $2$ và tiếp tế tại trạm $2$. Tiếp theo, chú dùng con đường thứ hai đi từ trạm $2$ đến trạm $3$. Cuối cùng, chú dùng con đường thứ ba đi từ trạm $3$ đến trạm $1$ và tiếp tế tại trạm $1$. Cách này mất $3$ giờ để thực hiện kế hoạch. Vì đây là thời gian ít nhất nên in 3.

Lưu ý rằng JOI-kun không thể di chuyển giữa các trạm theo lộ trình $1 \to 2 \to 1$ vì chú không thể quay đầu.

Dữ liệu vào 2

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

Dữ liệu ra 2

5
2
3
-1

Ghi chú

Trong ví dụ 2, kế hoạch của ngày thứ nhất là $4,1,4$. Đầu tiên, JOI-kun tiếp tế tại trạm $4$. Sau đó, chú dùng con đường thứ tư đi từ trạm $4$ đến trạm $1$ và tiếp tế tại trạm $1$. Tiếp theo, chú lần lượt dùng các con đường thứ nhất, thứ hai, thứ ba và thứ tư để đi theo lộ trình $1 \to 2 \to 3 \to 1 \to 4$ và tiếp tế tại trạm $4$. Cách này mất thời gian ít nhất.

Kế hoạch của ngày thứ tư là $2,4,2$. Vì JOI-kun không thể thực hiện kế hoạch này nên in -1.

Dữ liệu vào 3

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

Dữ liệu ra 3

38