Gegeben ist ein Graph mit $N$ Knoten und $M$ ungerichteten Kanten. Jede Kante $i$ hat eine Durchgangswertung von $W_i$ und verbindet die Knoten $U_i$ und $V_i$.

Bob darf sich mithilfe der Kanten von einem Knoten zum anderen bewegen. Bob kann die $i$-te Kante genau dann benutzen, wenn seine Wertung größer oder gleich $W_i$ ist. Er kann dieselbe Kante beliebig oft benutzen und denselben Knoten beliebig oft besuchen.

Immer wenn sich Bob bei Knoten $x$ befindet, hat er zwei Möglichkeiten, zusätzliche Wertung zu erhalten:

• Er kann kostenlos $A_x$ Wertung erhalten. Er kann diese Option während seiner gesamten Reise nur einmal nutzen.
• Er kann für $C_x$ Münzen $1$ Wertung erhalten. Er kann diese Option während seiner gesamten Reise beliebig oft nutzen.

Bob hat nun $Q$ Anfragen. Beantworte für jede Anfrage $i$ die folgende Frage:

• Bob hat eine Anfangswertung von $R_i$ und befindet sich bei Knoten $S_i$. Er plant, Knoten $T_i$ zu erreichen. Was ist die minimale Anzahl an Münzen, die dafür benötigt wird?

Gib $-1$ aus, falls er Knoten $T_i$ selbst mit unendlich vielen Münzen nicht erreichen kann.

Eingabe

• Die erste Zeile enthält eine ganze Zahl $T$ ($1 \le T \le 100$), die Anzahl der Testfälle.
• Danach gilt für jeden Testfall:
  • Die erste Zeile enthält drei durch Leerzeichen getrennte ganze Zahlen $N, M, Q$ ($1 \le N, M, Q \le 5 \cdot 10^5$).
  • Die zweite Zeile enthält $N$ durch Leerzeichen getrennte ganze Zahlen $A_1, A_2, \dots, A_N$ ($1 \le A_i \le 10^6$).
  • Die dritte Zeile enthält $N$ durch Leerzeichen getrennte ganze Zahlen $C_1, C_2, \dots, C_N$ ($1 \le C_i \le 10^6$).
  • Darauf folgen $M$ Zeilen, die jeweils drei durch Leerzeichen getrennte ganze Zahlen $U_i, V_i, W_i$ ($1 \le U_i, V_i \le N; 1 \le W_i \le 10^{12}$) enthalten.
  • Darauf folgen $Q$ Zeilen, die jeweils drei durch Leerzeichen getrennte ganze Zahlen $S_i, T_i, R_i$ ($1 \le S_i, T_i \le N; 1 \le R_i \le 10^{12}$) enthalten.

Es wird garantiert, dass die Summe von $N$ über alle Testfälle $5 \cdot 10^5$ nicht überschreitet.

Es wird garantiert, dass die Summe von $M$ über alle Testfälle $5 \cdot 10^5$ nicht überschreitet.

Es wird garantiert, dass die Summe von $Q$ über alle Testfälle $5 \cdot 10^5$ nicht überschreitet.

Ausgabe

Gib für jeden Testfall $Q$ Zeilen aus, die jeweils aus einer ganzen Zahl bestehen — der Antwort auf die jeweilige Anfrage.

Beispiel

Beispieleingabe 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

Beispielausgabe 1

11
0
4
5