JOI-kun est un sanglier qui vit dans IOI Forest, qui possède $N$ postes de ravitaillement et $M$ routes. Les postes sont numérotés de $1$ à $N$. La $i$-ème route ($1 \le i \le M$) relie les postes $A_i$ et $B_i$ dans les deux sens, et JOI-kun met $C_i$ heures pour la parcourir dans un sens comme dans l'autre. Il est possible de se rendre de n'importe quel poste à n'importe quel autre en empruntant une ou plusieurs routes.

JOI-kun ne sait pas bien faire demi-tour. Il ne peut pas faire demi-tour au milieu d'une route pour revenir au poste d'où il vient. De plus, lorsqu'il arrive à un poste par une route, il ne peut pas emprunter cette même route pour revenir au poste où il se trouvait juste avant.

Chaque jour, JOI-kun distribue de la nourriture aux postes selon un plan de ravitaillement. Le plan d'une journée est une suite de $L$ postes $X_1,X_2,\ldots,X_L$. Il commence sa distribution au poste $X_1$, visite les postes dans cet ordre et termine sa distribution au poste $X_L$. Il peut passer par d'autres postes en chemin. Il est possible qu'il doive distribuer de la nourriture plusieurs fois au même poste, mais $X_j \ne X_{j+1}$ pour tout $j$ ($1 \le j \le L-1$). Il peut exister des plans de ravitaillement qu'il ne peut pas exécuter.

Au début, JOI-kun détermine le plan de ravitaillement initial $X_1,X_2,\ldots,X_L$. Le matin du $k$-ème jour ($1 \le k \le T$), il remplace la $P_k$-ème valeur du plan par $Q_k$ (autrement dit, $X_{P_k}$ devient $Q_k$), puis distribue la nourriture selon le nouveau plan. Il est garanti qu'après cette modification, $X_j \ne X_{j+1}$ pour tout $j$ ($1 \le j \le L-1$).

Pour chacun des plans des $T$ jours, JOI-kun souhaite déterminer s'il peut l'exécuter et, si c'est le cas, trouver le temps minimal possible pour distribuer la nourriture selon ce plan.

Tâche

Étant données les informations sur IOI Forest et les plans de ravitaillement de JOI-kun, écrivez un programme qui, pour chacun des plans des $T$ jours, détermine s'il peut l'exécuter et, si c'est le cas, trouve le temps minimal possible pour distribuer la nourriture selon ce plan.

Entrée

Lisez les données suivantes sur l'entrée standard.

• La première ligne contient quatre entiers $N$, $M$, $T$ et $L$ séparés par des espaces. Cela signifie que IOI Forest possède $N$ postes de ravitaillement et $M$ routes, que JOI-kun considère les plans de $T$ jours et qu'un plan est une suite de longueur $L$.
• La $i$-ème des $M$ lignes suivantes ($1 \le i \le M$) contient trois entiers $A_i$, $B_i$ et $C_i$ séparés par des espaces. Cela signifie que la $i$-ème route relie les postes $A_i$ et $B_i$ dans les deux sens et que JOI-kun met $C_i$ heures pour la parcourir dans un sens comme dans l'autre.
• La $j$-ème des $L$ lignes suivantes ($1 \le j \le L$) contient un entier $X_j$. Le plan initial est donc $X_1,X_2,\ldots,X_L$.
• La $k$-ème des $T$ lignes suivantes ($1 \le k \le T$) contient deux entiers $P_k$ et $Q_k$ séparés par un espace. Cela signifie que JOI-kun remplace la $P_k$-ème valeur du plan par $Q_k$ le matin du $k$-ème jour.

Sortie

Écrivez $T$ lignes sur la sortie standard. La $k$-ème ligne ($1 \le k \le T$) doit contenir $-1$ s'il ne peut pas exécuter le plan du $k$-ème jour, ou le temps minimal possible, en heures, pour l'exécuter si c'est possible.

Contraintes

Toutes les données d'entrée satisfont les conditions suivantes.

• $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$).
• Il est possible de se rendre de n'importe quel poste à n'importe quel autre en empruntant une ou plusieurs routes.
• $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$).
• Pour tout $j$ ($1 \le j \le L-1$), $X_j \ne X_{j+1}$. Après chaque modification du plan, on a également $X_j \ne X_{j+1}$ pour tout $j$ ($1 \le j \le L-1$).

Sous-tâches

Il y a 4 sous-tâches. Le nombre de points et les contraintes supplémentaires de chacune sont les suivants :

Sous-tâche 1 [12 points]

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

Sous-tâche 2 [35 points]

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

Sous-tâche 3 [15 points]

• $T=1$.

Sous-tâche 4 [38 points]

Il n'y a pas de contrainte supplémentaire.

Exemples

Entrée 1

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

Sortie 1

3

Remarque

Dans le premier exemple, le plan initial est $1,2,3$. Le matin du premier jour, JOI-kun remplace la troisième valeur de ce plan par $1$. Le plan du premier jour est donc $1,2,1$.

JOI-kun distribue d'abord de la nourriture au poste $1$. Ensuite, il emprunte la première route pour aller du poste $1$ au poste $2$ et y distribue de la nourriture. Puis il emprunte la deuxième route pour aller du poste $2$ au poste $3$. Enfin, il emprunte la troisième route pour aller du poste $3$ au poste $1$ et y distribue de la nourriture. Ainsi, l'exécution du plan prend $3$ heures. Comme il s'agit du temps minimal possible, affichez 3.

Notez que JOI-kun ne peut pas suivre le trajet $1 \to 2 \to 1$, car il ne peut pas faire demi-tour.

Entrée 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

Sortie 2

5
2
3
-1

Remarque

Dans le deuxième exemple, le plan du premier jour est $4,1,4$. JOI-kun distribue d'abord de la nourriture au poste $4$. Ensuite, il emprunte la quatrième route pour aller du poste $4$ au poste $1$ et y distribue de la nourriture. Puis il emprunte les première, deuxième, troisième et quatrième routes dans cet ordre pour suivre le trajet $1 \to 2 \to 3 \to 1 \to 4$ et distribue de la nourriture au poste $4$. Cela prend le temps minimal possible.

Le plan du quatrième jour est $2,4,2$. Comme JOI-kun ne peut pas exécuter ce plan, affichez -1.

Entrée 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

Sortie 3

38