JOI-kun es un jabalí que vive en IOI Forest, donde hay $N$ puestos de comida y $M$ caminos. Los puestos están numerados del $1$ al $N$. El camino $i$-ésimo ($1 \le i \le M$) conecta los puestos $A_i$ y $B_i$ en ambos sentidos, y JOI-kun tarda $C_i$ horas en recorrerlo en cualquiera de los dos sentidos. Es posible ir de cualquier puesto a cualquier otro usando uno o más caminos.

A JOI-kun se le da mal dar media vuelta. No puede dar media vuelta a mitad de un camino para regresar al puesto donde estaba. Además, cuando llega a un puesto por un camino, no puede recorrer ese mismo camino para volver al puesto donde estaba justo antes.

Todos los días, JOI-kun abastece los puestos de comida según un plan de abastecimiento. El plan de un día consiste en una secuencia de $L$ puestos $X_1,X_2,\ldots,X_L$. Comienza a abastecer en el puesto $X_1$, visita los puestos en este orden y termina de abastecer en el puesto $X_L$. Puede pasar por otros puestos entre medias. Es posible que deba abastecer un mismo puesto varias veces, pero se cumple $X_j \ne X_{j+1}$ para cada $j$ ($1 \le j \le L-1$). Ten en cuenta que puede haber planes de abastecimiento que no pueda ejecutar.

Al principio, JOI-kun determina el plan inicial $X_1,X_2,\ldots,X_L$. La mañana del día $k$-ésimo ($1 \le k \le T$) cambiará el valor en la posición $P_k$ del plan por $Q_k$ (es decir, $X_{P_k}$ pasa a ser $Q_k$) y después abastecerá según el nuevo plan. Se garantiza que tras el cambio se cumple $X_j \ne X_{j+1}$ para cada $j$ ($1 \le j \le L-1$).

Para cada plan de los $T$ días, JOI-kun quiere determinar si puede ejecutarlo y, si puede, hallar el mínimo tiempo posible para abastecer según ese plan.

Tarea

Dados los datos de IOI Forest y los planes de abastecimiento de JOI-kun, escribe un programa que, para cada plan de los $T$ días, determine si puede ejecutarlo y, si puede, halle el mínimo tiempo posible para abastecer según ese plan.

Entrada

Lee los siguientes datos de la entrada estándar.

• La primera línea contiene cuatro enteros separados por espacios: $N,M,T,L$. Esto significa que hay $N$ puestos y $M$ caminos en IOI Forest, JOI-kun considera planes para $T$ días y el plan consiste en una secuencia de longitud $L$.
• La línea $i$-ésima ($1 \le i \le M$) de las siguientes $M$ líneas contiene tres enteros separados por espacios: $A_i,B_i,C_i$. Esto significa que el camino $i$-ésimo conecta los puestos $A_i$ y $B_i$ en ambos sentidos, y JOI-kun tarda $C_i$ horas en recorrerlo en cualquiera de los dos sentidos.
• La línea $j$-ésima ($1 \le j \le L$) de las siguientes $L$ líneas contiene un entero $X_j$. Esto significa que el plan inicial es $X_1,X_2,\ldots,X_L$.
• La línea $k$-ésima ($1 \le k \le T$) de las siguientes $T$ líneas contiene dos enteros separados por un espacio: $P_k,Q_k$. Esto significa que JOI-kun cambiará el valor en la posición $P_k$ del plan por $Q_k$ la mañana del día $k$-ésimo.

Salida

Escribe $T$ líneas en la salida estándar. La línea $k$-ésima ($1 \le k \le T$) debe contener -1 si no puede ejecutar el plan del día $k$-ésimo o, si puede, el mínimo tiempo posible en horas para ejecutarlo.

Restricciones

Todos los datos de entrada satisfacen las siguientes condiciones.

• $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$).
• Es posible ir de cualquier puesto a cualquier otro usando uno o más caminos.
• $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$).
• Se cumple $X_j \ne X_{j+1}$ para cada $j$ ($1 \le j \le L-1$). También después de cada cambio del plan se cumple $X_j \ne X_{j+1}$ para cada $j$ ($1 \le j \le L-1$).

Subtareas

Hay 4 subtareas. La puntuación y las restricciones adicionales de cada subtarea son las siguientes:

Subtarea 1 [12 puntos]

• $N \le 10$.
• $M \le 10$.
• $T=1$.
• $L \le 10$.
• $C_i \le 10$ ($1 \le i \le M$).

Subtarea 2 [35 puntos]

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

Subtarea 3 [15 puntos]

• $T=1$.

Subtarea 4 [38 puntos]

No hay restricciones adicionales.

Ejemplos

Entrada 1

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

Salida 1

3

Nota

En el ejemplo de entrada 1, el plan inicial es $1,2,3$. JOI-kun cambia el tercer valor del plan por $1$ la mañana del primer día. Por tanto, el plan del primer día es $1,2,1$.

Primero, JOI-kun abastecerá el puesto $1$. A continuación, usará el primer camino para ir del puesto $1$ al puesto $2$ y abastecerá el puesto $2$. Después, usará el segundo camino para ir del puesto $2$ al puesto $3$. Por último, usará el tercer camino para ir del puesto $3$ al puesto $1$ y abastecerá el puesto $1$. De esta forma tardará 3 horas en ejecutar el plan. Como este es el mínimo tiempo posible, se debe imprimir 3.

Ten en cuenta que JOI-kun no puede recorrer los puestos $1 \to 2 \to 1$ porque no puede dar media vuelta.

Entrada 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

Salida 2

5
2
3
-1

Nota

En el ejemplo de entrada 2, el plan del primer día es $4,1,4$. Primero, JOI-kun abastecerá el puesto $4$. A continuación, usará el cuarto camino para ir del puesto $4$ al puesto $1$ y abastecerá el puesto $1$. Después, usará los caminos primero, segundo, tercero y cuarto, en ese orden, para recorrer los puestos $1 \to 2 \to 3 \to 1 \to 4$ y abastecerá el puesto $4$. Esto requiere el mínimo tiempo posible.

El plan del cuarto día es $2,4,2$. Como JOI-kun no puede ejecutar este plan, se debe imprimir -1.

Entrada 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

Salida 3

38