On vous donne un graphe comportant $N$ sommets et $M$ arêtes non orientées. Chaque arête $i$ a un classement de passage $W_i$ et relie les sommets $U_i$ et $V_i$.

Bob est autorisé à se déplacer d'un sommet à un autre en empruntant les arêtes. Bob peut emprunter la $i$-ième arête si et seulement si son classement est supérieur ou égal à $W_i$. Il peut emprunter la même arête et visiter le même sommet autant de fois qu'il le souhaite.

Chaque fois que Bob se trouve au sommet $x$, il dispose de deux options pour augmenter son classement :

• Il peut gagner $A_x$ points de classement gratuitement. Il ne peut utiliser cette option qu'une seule fois au cours de son trajet.
• Il peut gagner $1$ point de classement pour $C_x$ pièces. Il peut utiliser cette option autant de fois qu'il le souhaite tout au long de son trajet.

Bob a maintenant $Q$ requêtes. Pour chaque requête $i$, répondez à la question suivante :

• Bob a un classement initial de $R_i$ et se trouve au sommet $S_i$. Il prévoit d'atteindre le sommet $T_i$. Quel est le nombre minimum de pièces nécessaires pour cela ?

Affichez $-1$ s'il ne peut pas atteindre le sommet $T_i$ même avec un nombre infini de pièces.

Entrée

• La première ligne contient un entier $T$ ($1 \le T \le 100$), le nombre de cas de test.
• Ensuite, pour chaque cas de test :
  • La première ligne contient trois entiers séparés par des espaces $N, M, Q$ ($1 \le N, M, Q \le 5 \cdot 10^5$).
  • La deuxième ligne contient $N$ entiers séparés par des espaces $A_1, A_2, \dots, A_N$ ($1 \le A_i \le 10^6$).
  • La troisième ligne contient $N$ entiers séparés par des espaces $C_1, C_2, \dots, C_N$ ($1 \le C_i \le 10^6$).
  • Viennent ensuite $M$ lignes, contenant chacune trois entiers séparés par des espaces $U_i, V_i, W_i$ ($1 \le U_i, V_i \le N; 1 \le W_i \le 10^{12}$).
  • Viennent ensuite $Q$ lignes, contenant chacune trois entiers séparés par des espaces $S_i, T_i, R_i$ ($1 \le S_i, T_i \le N; 1 \le R_i \le 10^{12}$).

Il est garanti que la somme de $N$ sur l'ensemble des cas de test ne dépasse pas $5 \cdot 10^5$.

Il est garanti que la somme de $M$ sur l'ensemble des cas de test ne dépasse pas $5 \cdot 10^5$.

Il est garanti que la somme de $Q$ sur l'ensemble des cas de test ne dépasse pas $5 \cdot 10^5$.

Sortie

Pour chaque cas de test, affichez $Q$ lignes, chacune composée d'un seul entier, la réponse à cette requête.

Exemple

Exemple d'entrée 1

1
5 5 4
5 2 4 3 10
1 2 3 4 5
3 3 10
1 2 5
3 4 7
1 3 13
2 5 21
4 5 3
2 2 4
1 4 2
5 2 10

Exemple de sortie 1

11
0
4
5