JOI 군은 $N$개의 먹이통과 $M$개의 길이 있는 IOI 숲에 사는 멧돼지이다. 먹이통에는 $1$부터 $N$까지 번호가 매겨져 있다. $i$번째 길($1 \le i \le M$)은 먹이통 $A_i$와 $B_i$를 양방향으로 연결하며, JOI 군이 이 길을 따라 어느 한쪽 방향으로 이동하는 데는 $C_i$시간이 걸린다. 하나 이상의 길을 사용하여 임의의 먹이통에서 다른 임의의 먹이통으로 이동하는 것이 가능하다.

JOI 군은 유턴을 잘하지 못한다. 그는 길 도중에 유턴하여 자신이 있던 먹이통으로 되돌아갈 수 없다. 게다가 어떤 길을 사용하여 먹이통에 도착했을 때, 방금 지나온 그 길을 그대로 다시 따라가서 직전에 있던 먹이통으로 되돌아갈 수도 없다.

매일 JOI 군은 공급 계획에 따라 먹이통에 먹이를 공급한다. 하루의 공급 계획은 $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 군은 초기 공급 계획 $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 군은 자신이 그 공급 계획을 실행할 수 있는지 여부를 판별하고, 만약 실행할 수 있다면 공급 계획에 따라 먹이를 공급하는 데 걸리는 최소 시간을 구하고 싶어 한다.

과제

IOI 숲의 데이터와 JOI 군의 공급 계획들이 주어졌을 때, $T$일간의 각 공급 계획에 대해 그가 공급 계획을 실행할 수 있는지 여부를 판별하고, 실행할 수 있다면 공급 계획에 따라 먹이를 공급하는 데 걸리는 최소 시간을 구하는 프로그램을 작성하시오.

입력

표준 입력으로부터 다음 데이터를 읽어들인다.

• 입력의 첫째 줄에는 공백으로 구분된 네 정수 $N$, $M$, $T$, $L$이 주어진다. 이는 IOI 숲에 $N$개의 먹이통과 $M$개의 길이 있으며, JOI 군이 $T$일 동안의 공급 계획을 고려하고, 공급 계획이 길이 $L$인 수열로 이루어져 있음을 의미한다.
• 이어지는 $M$개의 줄 중 $i$번째 줄($1 \le i \le M$)에는 공백으로 구분된 세 정수 $A_i$, $B_i$, $C_i$가 주어진다. 이는 $i$번째 길이 먹이통 $A_i$와 $B_i$를 양방향으로 연결하며, JOI 군이 이 길을 따라 어느 한쪽 방향으로 이동하는 데 $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 군이 $k$번째 날 아침에 공급 계획의 $P_k$번째 값을 $Q_k$로 변경함을 의미한다.

출력

표준 출력에 $T$개의 줄을 출력한다. $k$번째 줄($1 \le k \le T$)에는 그가 $k$번째 날에 공급 계획을 실행할 수 없다면 $-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 군은 첫째 날 아침에 이 공급 계획의 3번째 값을 $1$로 변경한다. 따라서 첫째 날의 공급 계획은 $1,2,1$이다.

먼저 JOI 군은 먹이통 $1$에 먹이를 공급한다. 다음으로, 1번째 길을 사용하여 먹이통 $1$에서 먹이통 $2$로 이동한 뒤 먹이통 $2$에 먹이를 공급한다. 그다음, 2번째 길을 사용하여 먹이통 $2$에서 먹이통 $3$으로 이동한다. 마지막으로, 3번째 길을 사용하여 먹이통 $3$에서 먹이통 $1$로 이동한 뒤 먹이통 $1$에 먹이를 공급한다. 이렇게 하면 공급 계획을 실행하는 데 3시간이 걸린다. 이것이 가능한 최소 시간이므로 3을 출력한다.

JOI 군은 유턴을 할 수 없기 때문에 먹이통을 $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에서, 첫째 날의 공급 계획은 $4,1,4$이다. 먼저 JOI 군은 먹이통 $4$에 먹이를 공급한다. 다음으로, 4번째 길을 사용하여 먹이통 $4$에서 먹이통 $1$로 이동한 뒤 먹이통 $1$에 먹이를 공급한다. 그다음, 1번째, 2번째, 3번째, 4번째 길을 차례대로 사용하여 먹이통을 $1 \to 2 \to 3 \to 1 \to 4$로 이동한 뒤 먹이통 $4$에 먹이를 공급한다. 이것이 최소 시간이 걸리는 방법이다.

넷째 날의 공급 계획은 $2,4,2$이다. JOI 군은 이 공급 계획을 실행할 수 없으므로 -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