Dany jest graf o $N$ wierzchołkach i $M$ nieskierowanych krawędziach. Każda krawędź $i$ ma wymagany ranking przejścia równy $W_i$ i łączy wierzchołki $U_i$ oraz $V_i$.

Bob może przemieszczać się między wierzchołkami za pomocą krawędzi. Bob może skorzystać z $i$-tej krawędzi wtedy i tylko wtedy, gdy jego ranking jest większy lub równy $W_i$. Może korzystać z tej samej krawędzi i odwiedzać ten sam wierzchołek dowolnie wiele razy.

Za każdym razem, gdy Bob znajduje się w wierzchołku $x$, ma dwie możliwości zdobycia nowego rankingu:

• Może zdobyć $A_x$ rankingu za darmo. Z tej opcji może skorzystać tylko raz podczas całej podróży.
• Może zdobyć $1$ punkt rankingu za $C_x$ monet. Z tej opcji może korzystać dowolnie wiele razy podczas całej podróży.

Bob ma teraz $Q$ zapytań. Dla każdego zapytania $i$ odpowiedz na następujące pytanie:

• Bob ma początkowy ranking równy $R_i$ i znajduje się w wierzchołku $S_i$. Planuje dotrzeć do wierzchołka $T_i$. Jaka jest minimalna liczba monet potrzebna do osiągnięcia tego celu?

Wypisz $-1$, jeśli nie może dotrzeć do wierzchołka $T_i$ nawet dysponując nieskończoną liczbą monet.

Wejście

• Pierwszy wiersz zawiera jedną liczbę całkowitą $T$ ($1 \le T \le 100$), liczbę przypadków testowych.
• Następnie dla każdego przypadku testowego:
  • Pierwszy wiersz zawiera trzy oddzielone spacjami liczby całkowite $N, M, Q$ ($1 \le N, M, Q \le 5 \cdot 10^5$).
  • Drugi wiersz zawiera $N$ oddzielonych spacjami liczb całkowitych $A_1, A_2, \dots, A_N$ ($1 \le A_i \le 10^6$).
  • Trzeci wiersz zawiera $N$ oddzielonych spacjami liczb całkowitych $C_1, C_2, \dots, C_N$ ($1 \le C_i \le 10^6$).
  • Następnie podanych jest $M$ wierszy, z których każdy zawiera trzy oddzielone spacjami liczby całkowite $U_i, V_i, W_i$ ($1 \le U_i, V_i \le N; 1 \le W_i \le 10^{12}$).
  • Następnie podanych jest $Q$ wierszy, z których każdy zawiera trzy oddzielone spacjami liczby całkowite $S_i, T_i, R_i$ ($1 \le S_i, T_i \le N; 1 \le R_i \le 10^{12}$).

Gwarantuje się, że suma $N$ po wszystkich przypadkach testowych nie przekracza $5 \cdot 10^5$.

Gwarantuje się, że suma $M$ po wszystkich przypadkach testowych nie przekracza $5 \cdot 10^5$.

Gwarantuje się, że suma $Q$ po wszystkich przypadkach testowych nie przekracza $5 \cdot 10^5$.

Wyjście

Dla każdego przypadku testowego wypisz $Q$ wierszy, z których każdy składa się z jednej liczby całkowitej — odpowiedzi na dane zapytanie.

Przykład

Przykładowe wejście 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

Przykładowe wyjście 1

11
0
4
5