17691번 - Wild Boar 서브태스크다국어

JOI-kun is a wild boar living in IOI Forest, which has N food stations and M roads. The food stations are numbered 1 through N. The i-th road (1 ≤ i ≤ M) connects food stations A_i and B_i in both directions, and it takes C_i hours for JOI-kun to go along this road in either direction. It is possible to go from any food station to any other using one or more roads.

JOI-kun is poor at U-turning. He cannot U-turn halfway on a road to return to the food station where he was. Moreover, when he arrives at a food station using a road, he cannot go along that road to return to the food station where he was just before.

Every day, JOI-kun supplies food at food stations according to the supply plan. The supply plan for a day consists of a sequence of L food stations X₁, X₂, . . . , X_L. He starts supplying at food station X₁, visits food stations in this order, and ends supplying at food station X_L. He is allowed to go via other food stations in the middle. It is possible that he is to supply at a food station multiple times, but X_j ≠ X_j+1 holds for each j (1 ≤ j ≤ L − 1). Note that there might exist a supply plan which he cannot execute.

At the beginning, JOI-kun determines the initial supply plan X₁, X₂, . . . , X_L. He will change the P_k-th value of the supply plan into Q_k (i.e. X_Pk becomes Q_k) on the morning of the k-th day (1 ≤ k ≤ T), and then supply food according to the new supply plan. It is assured that X_j ≠ X_j+1 holds for each j (1 ≤ j ≤ L − 1) after the change.

For each supply plan for the T days, JOI-kun wants to determine whether he can execute the supply plan or not, and, if he can, to find the minimum possible time to supply foods according to the supply plan.

Given the data of IOI Forest and JOI-kun’s supply plans, for each supply plan for the T days, write a program which determines whether he can execute the supply plan or not, and, if he can, finds the minimum possible time to supply foods according to the supply plan.

Read the following data from the standard input.

• The first line of the input contains four space separated integers N, M, T and L. This means that there are N food stations and M roads in IOI Forest, JOI-kun considers supply plans for T days, and the supply plan consists of a sequence of length L.
• The i-th line (1 ≤ i ≤ M) of the following M lines contains three space separated integers A_i, B_i and C_i. This means that the i-th road connects food stations A_i and B_i in both directions, and it takes C_i hours for JOI-kun to go along this road in either directions.
• The j-th line (1 ≤ j ≤ L) of the following L lines contains an integer X_j. This means the initial supply plan is X₁, X₂, . . . , X_L.
• The k-th line (1 ≤ k ≤ T) of the following T lines contains two space separated integers P_k and Q_k. This means that JOI-kun will change the P_k-th value of the supply plan into Q_k on the morning of the k-th day

Write T lines to the standard output. The k-th line (1 ≤ k ≤ T) should contain -1 if he cannot execute the supply plan on the k-th day, or the minimum possible time in hours to execute it if he can.

• 2 ≤ N ≤ 2 000.
• N − 1 ≤ M ≤ 2 000.
• 1 ≤ T ≤ 100 000.
• 2 ≤ L ≤ 100 000.
• 1 ≤ A_i < B_i ≤ N (1 ≤ i ≤ M).
• (A_i, B_i), (A_j, B_j) (1 ≤ i < j ≤ M).
• It is possible to go from any food station to any other using one or more roads.
• 1 ≤ C_i ≤ 1 000 000 000 (1 ≤ i ≤ M).
• 1 ≤ Xj ≤ N (1 ≤ j ≤ L).
• 1 ≤ P_k ≤ L (1 ≤ k ≤ T).
• 1 ≤ Q_k ≤ N (1 ≤ k ≤ T).
• X_j ≠ X_j+1 holds for each j (1 ≤ j ≤ L − 1). Also after each change of the supply plan, X_j ≠ X_j+1 holds for each j (1 ≤ j ≤ L − 1).

• N ≤ 10.
• M ≤ 10.
• T = 1.
• L ≤ 10.
• C_i ≤ 10 (1 ≤ i ≤ M).

• N ≤ 500.
• M ≤ 500.
• T = 1.

• T = 1.

There are no additional constraints.