JOI-kun 是一隻住在 IOI 森林裡的野豬。森林裡有 $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 森林的資料與 JOI-kun 的補給計畫，請撰寫程式，對於這 $T$ 天中每一天的補給計畫，判斷他是否能執行該計畫；如果可以，找出依照該計畫補充食物所需的最短時間。

輸入格式

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

• 輸入的第一行包含四個以空格分隔的整數 $N$、$M$、$T$ 與 $L$。這表示 IOI 森林裡有 $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$ 行。如果他無法執行第 $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\to2\to1$ 的順序移動，因為他不能迴轉。

輸入格式 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\to2\to3\to1\to4$ 的順序移動，並在補給站 $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