야생 멧돼지

JOI-kun은 IOI 숲에 사는 야생 멧돼지입니다. 이 숲에는 먹이 공급소 N곳과 도로 M개가 있습니다. 공급소는 1번부터 N번까지 번호가 매겨져 있습니다. i번째 도로(1 ≤ i ≤ M)는 공급소 Ai와 Bi를 양방향으로 잇고, 어느 방향으로 지나든 Ci시간이 걸립니다. 어떤 공급소에서든 도로를 하나 이상 거쳐 다른 모든 공급소로 갈 수 있습니다.

JOI-kun은 U턴에 서툽니다. 도로 중간에서 U턴해 온 공급소로 되돌아갈 수 없습니다. 도로를 타고 공급소에 도착하면, 방금 떠나온 공급소로 되돌아가는 그 도로는 탈 수 없습니다.

매일 JOI-kun은 공급 계획에 따라 공급소에 먹이를 줍니다. 공급 계획은 길이 L인 공급소 순서열 X1, X2, ..., XL입니다. X1에서 공급을 시작해 이 순서대로 공급소를 방문하고, XL에서 공급을 마칩니다. 그 사이 다른 공급소를 지나가도 됩니다. 같은 공급소가 계획에 여러 번 나와도 되지만, 각 j(1 ≤ j ≤ L-1)에 대해 Xj ≠ Xj+1이어야 합니다. 실행할 수 없는 공급 계획도 있습니다.

처음에 JOI-kun은 초기 공급 계획 X1, ..., XL을 정합니다. k일째 아침(1 ≤ k ≤ T)에 계획의 Pk번째 값을 Qk로 바꾸고(XPk가 Qk가 됨), 바뀐 계획에 따라 먹이를 줍니다. 변경 후에도 각 j(1 ≤ j ≤ L-1)에 대해 Xj ≠ Xj+1이 성립합니다.

T일 동안의 공급 계획 각각에 대해 실행할 수 있는지 판단하세요. 실행할 수 있다면 순서대로 공급을 마치는 데 걸리는 최소 시간을 구하세요.

첫째 줄에 정수 N, M, T, L이 공백으로 구분되어 주어집니다. 각각 공급소의 수, 도로의 수, 날짜 수, 공급 계획의 길이입니다.

이어지는 M개의 줄에는 도로를 나타내는 정수 Ai, Bi, Ci가 공백으로 구분되어 주어집니다.

이어지는 L개의 줄에는 초기 공급 계획을 한 줄에 정수 Xj 하나씩 줍니다.

마지막 T개의 줄에는 정수 Pk와 Qk가 공백으로 구분되어 주어집니다. k일째에는 계획의 Pk번째 값이 Qk로 바뀝니다.

T개의 줄을 출력합니다. k번째 줄에는 k일째 공급 계획을 실행할 수 없으면 -1을, 실행할 수 있으면 실행에 필요한 최소 시간(시간 단위)을 출력합니다.

• 2 ≤ N ≤ 2 000
• N − 1 ≤ M ≤ 2 000
• 1 ≤ T ≤ 100 000
• 2 ≤ L ≤ 100 000
• 1 ≤ Ai < Bi ≤ N (1 ≤ i ≤ M)
• i ≠ j이면 (Ai, Bi)와 (Aj, Bj)는 같은 쌍이 아닙니다.
• 어떤 공급소에서든 도로를 하나 이상 거쳐 다른 모든 공급소로 갈 수 있습니다.
• 1 ≤ Ci ≤ 1 000 000 000 (1 ≤ i ≤ M)
• 1 ≤ Xj ≤ N (1 ≤ j ≤ L)
• 1 ≤ Pk ≤ L (1 ≤ k ≤ T)
• 1 ≤ Qk ≤ N (1 ≤ k ≤ T)
• 계획을 바꾼 뒤에도 각 j(1 ≤ j ≤ L-1)에 대해 Xj ≠ Xj+1이 성립합니다.