JOI-kun é um javali que vive na IOI Forest, onde há $N$ postos de alimentação e $M$ estradas. Os postos são numerados de $1$ a $N$. A estrada $i$ ($1 \le i \le M$) liga os postos $A_i$ e $B_i$ nos dois sentidos, e JOI-kun demora $C_i$ horas a percorrê-la em qualquer sentido. É possível ir de qualquer posto a qualquer outro usando uma ou mais estradas.

JOI-kun tem dificuldade em fazer inversão de marcha. Não pode inverter a marcha a meio de uma estrada para regressar ao posto onde estava. Além disso, ao chegar a um posto por uma estrada, não pode percorrer essa mesma estrada para regressar ao posto onde estava imediatamente antes.

Todos os dias, JOI-kun abastece os postos com alimentos de acordo com um plano de abastecimento. O plano de um dia consiste numa sequência de $L$ postos $X_1,X_2,\ldots,X_L$. Ele começa a abastecer no posto $X_1$, visita os postos nesta ordem e termina o abastecimento no posto $X_L$. Pode passar por outros postos pelo caminho. É possível que tenha de abastecer o mesmo posto várias vezes, mas $X_j \ne X_{j+1}$ para cada $j$ ($1 \le j \le L-1$). Note que pode existir um plano que ele não consiga executar.

Inicialmente, JOI-kun determina o plano de abastecimento inicial $X_1,X_2,\ldots,X_L$. Na manhã do dia $k$ ($1 \le k \le T$), substitui o valor na posição $P_k$ do plano por $Q_k$ (isto é, $X_{P_k}$ passa a ser $Q_k$) e depois abastece os postos de acordo com o novo plano. É garantido que $X_j \ne X_{j+1}$ para cada $j$ ($1 \le j \le L-1$) após a alteração.

Para cada plano dos $T$ dias, JOI-kun quer determinar se consegue executá-lo e, em caso afirmativo, encontrar o tempo mínimo possível para abastecer os postos de acordo com esse plano.

Tarefa

Dados os dados da IOI Forest e os planos de abastecimento de JOI-kun, escreva um programa que, para cada plano dos $T$ dias, determine se ele consegue executá-lo e, em caso afirmativo, encontre o tempo mínimo possível para abastecer os postos de acordo com esse plano.

Entrada

Leia os seguintes dados da entrada padrão.

• A primeira linha contém quatro inteiros $N$, $M$, $T$ e $L$, separados por espaços. Isto significa que há $N$ postos e $M$ estradas na IOI Forest, que JOI-kun considera planos para $T$ dias e que o plano consiste numa sequência de comprimento $L$.
• A linha $i$ ($1 \le i \le M$) das $M$ linhas seguintes contém três inteiros $A_i$, $B_i$ e $C_i$, separados por espaços. Isto significa que a estrada $i$ liga os postos $A_i$ e $B_i$ nos dois sentidos e que JOI-kun demora $C_i$ horas a percorrê-la em qualquer sentido.
• A linha $j$ ($1 \le j \le L$) das $L$ linhas seguintes contém um inteiro $X_j$. Isto significa que o plano inicial é $X_1,X_2,\ldots,X_L$.
• A linha $k$ ($1 \le k \le T$) das $T$ linhas seguintes contém dois inteiros $P_k$ e $Q_k$, separados por um espaço. Isto significa que JOI-kun substituirá o valor na posição $P_k$ do plano por $Q_k$ na manhã do dia $k$.

Saída

Escreva $T$ linhas na saída padrão. A linha $k$ ($1 \le k \le T$) deve conter $-1$ se ele não conseguir executar o plano do dia $k$, ou o tempo mínimo possível, em horas, para o executar, caso consiga.

Restrições

Todos os dados de entrada satisfazem as seguintes condições.

• $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$).
• É possível ir de qualquer posto a qualquer outro usando uma ou mais estradas.
• $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$).
• $X_j \ne X_{j+1}$ para cada $j$ ($1 \le j \le L-1$). Após cada alteração do plano, também se verifica $X_j \ne X_{j+1}$ para cada $j$ ($1 \le j \le L-1$).

Subtarefas

Há 4 subtarefas. A pontuação e as restrições adicionais de cada uma são as seguintes:

Subtarefa 1 [12 pontos]

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

Subtarefa 2 [35 pontos]

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

Subtarefa 3 [15 pontos]

• $T=1$.

Subtarefa 4 [38 pontos]

Não há restrições adicionais.

Exemplos

Entrada 1

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

Saída 1

3

Explicação

No exemplo de entrada 1, o plano inicial é $1,2,3$. JOI-kun substitui o terceiro valor deste plano por $1$ na manhã do primeiro dia. Portanto, o plano do primeiro dia é $1,2,1$.

Primeiro, JOI-kun abastece o posto $1$. Depois, usa a estrada $1$ para ir do posto $1$ ao posto $2$ e abastece o posto $2$. Em seguida, usa a estrada $2$ para ir do posto $2$ ao posto $3$. Por fim, usa a estrada $3$ para ir do posto $3$ ao posto $1$ e abastece o posto $1$. Assim, demora $3$ horas a executar o plano. Como este é o tempo mínimo possível, a saída é $3$.

Note que JOI-kun não pode percorrer os postos $1\to2\to1$, pois não pode inverter a marcha.

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

Saída 2

5
2
3
-1

Explicação

No exemplo de entrada 2, o plano do primeiro dia é $4,1,4$. Primeiro, JOI-kun abastece o posto $4$. Depois, usa a estrada $4$ para ir do posto $4$ ao posto $1$ e abastece o posto $1$. Em seguida, usa as estradas $1$, $2$, $3$ e $4$, nesta ordem, para percorrer os postos $1\to2\to3\to1\to4$ e abastece o posto $4$. Isto demora o tempo mínimo possível.

O plano do quarto dia é $2,4,2$. Como JOI-kun não consegue executar este plano, a saída é $-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

Saída 3

38