JOI-kun 係一隻住喺 IOI Forest 嘅野豬。森林有 $N$ 個食物站同 $M$ 條路。食物站由 $1$ 至 $N$ 編號。第 $i$ 條路（$1 \le i \le M$）雙向連接食物站 $A_i$ 同 $B_i$，JOI-kun 沿住呢條路行，無論邊個方向都要用 $C_i$ 個鐘。佢可以經一條或多條路，由任何一個食物站去到任何另一個食物站。

JOI-kun 唔擅長掉頭。佢唔可以喺一條路中途掉頭，返去原先嘅食物站。另外，當佢經一條路到達一個食物站之後，亦唔可以即刻沿同一條路返去啱啱離開嘅食物站。

每日，JOI-kun 都會跟住補給計劃去食物站補給食物。一日嘅補給計劃係一個由 $L$ 個食物站組成嘅序列 $X_1,X_2,\ldots,X_L$。佢由食物站 $X_1$ 開始補給，跟住按呢個次序到訪各個食物站，最後喺食物站 $X_L$ 完成補給。途中可以經過其他食物站。佢可能要喺同一個食物站補給多次，但每個 $j$（$1 \le j \le L-1$）都滿足 $X_j \ne X_{j+1}$。留意，有啲補給計劃可能係佢執行唔到嘅。

最初，JOI-kun 會定好初始補給計劃 $X_1,X_2,\ldots,X_L$。喺第 $k$ 日（$1 \le k \le T$）朝早，佢會將補給計劃嘅第 $P_k$ 個值改成 $Q_k$（即係將 $X_{P_k}$ 改成 $Q_k$），之後按新嘅補給計劃補給食物。保證修改之後，每個 $j$（$1 \le j \le L-1$）都滿足 $X_j \ne X_{j+1}$。

對於呢 $T$ 日每一日嘅補給計劃，JOI-kun 想知道自己可唔可以執行；如果可以，佢想搵出按計劃補給食物所需嘅最短時間。

任務

畀定 IOI Forest 嘅資料同 JOI-kun 嘅補給計劃，請寫一個程式，對於呢 $T$ 日每一日嘅補給計劃，判斷佢可唔可以執行；如果可以，就搵出按計劃補給食物所需嘅最短時間。

輸入格式

從標準輸入讀取以下資料。

• 第一行包含四個以空格分隔嘅整數 $N$、$M$、$T$ 同 $L$。即係 IOI Forest 有 $N$ 個食物站同 $M$ 條路，JOI-kun 考慮 $T$ 日嘅補給計劃，而每個計劃都係長度為 $L$ 嘅序列。
• 接落嚟 $M$ 行嘅第 $i$ 行（$1 \le i \le M$）包含三個以空格分隔嘅整數 $A_i$、$B_i$ 同 $C_i$。即係第 $i$ 條路雙向連接食物站 $A_i$ 同 $B_i$，JOI-kun 無論沿邊個方向行過呢條路，都要用 $C_i$ 個鐘。
• 接落嚟 $L$ 行嘅第 $j$ 行（$1 \le j \le L$）包含一個整數 $X_j$。即係初始補給計劃為 $X_1,X_2,\ldots,X_L$。
• 接落嚟 $T$ 行嘅第 $k$ 行（$1 \le k \le T$）包含兩個以空格分隔嘅整數 $P_k$ 同 $Q_k$。即係 JOI-kun 會喺第 $k$ 日朝早將補給計劃嘅第 $P_k$ 個值改成 $Q_k$。

輸出格式

向標準輸出寫出 $T$ 行。如果 JOI-kun 執行唔到第 $k$ 日嘅補給計劃，第 $k$ 行（$1 \le k \le T$）應該輸出 -1；如果可以，就輸出執行計劃所需嘅最短時間，以鐘為單位。

資料範圍

所有輸入資料都滿足以下條件。

• $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$）。
• 可以經一條或多條路，由任何一個食物站去到任何另一個食物站。
• $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$）。
• 每個 $j$（$1 \le j \le L-1$）都滿足 $X_j \ne X_{j+1}$。每次修改補給計劃之後，每個 $j$（$1 \le j \le L-1$）亦都滿足 $X_j \ne X_{j+1}$。

子任務

一共有 4 個子任務。各個子任務嘅分數同額外限制如下：

子任務 1 [12 分]

• $N \le 10$。
• $M \le 10$。
• $T=1$。
• $L \le 10$。
• $C_i \le 10$（$1 \le i \le M$）。

子任務 2 [35 分]

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

子任務 3 [15 分]

• $T=1$。

子任務 4 [38 分]

冇額外限制。

樣例

輸入格式 1

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

輸出格式 1

3

說明

喺樣例 1，初始補給計劃係 $1,2,3$。JOI-kun 喺第 $1$ 日朝早將計劃嘅第 $3$ 個值改成 $1$。所以，第 $1$ 日嘅補給計劃係 $1,2,1$。

首先，JOI-kun 喺食物站 $1$ 補給食物。跟住，佢沿第 $1$ 條路由食物站 $1$ 去到食物站 $2$，並喺食物站 $2$ 補給食物。然後，佢沿第 $2$ 條路由食物站 $2$ 去到食物站 $3$。最後，佢沿第 $3$ 條路由食物站 $3$ 去到食物站 $1$，並喺食物站 $1$ 補給食物。咁樣執行計劃一共要用 $3$ 個鐘。由於呢個係最短時間，所以輸出 $3$。

留意，JOI-kun 唔可以按 $1 \to 2 \to 1$ 嘅次序行過食物站，因為佢唔可以掉頭。

輸入格式 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

輸出格式 2

5
2
3
-1

說明

喺樣例 2，第 $1$ 日嘅補給計劃係 $4,1,4$。首先，JOI-kun 喺食物站 $4$ 補給食物。跟住，佢沿第 $4$ 條路由食物站 $4$ 去到食物站 $1$，並喺食物站 $1$ 補給食物。然後，佢按次序沿第 $1$、$2$、$3$ 同 $4$ 條路，按 $1 \to 2 \to 3 \to 1 \to 4$ 嘅次序行過食物站，並喺食物站 $4$ 補給食物。呢個方法所需嘅時間最短。

第 $4$ 日嘅補給計劃係 $2,4,2$。由於 JOI-kun 執行唔到呢個計劃，所以輸出 -1。

輸入格式 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

輸出格式 3

38