È dato un grafo con $N$ vertici e $M$ archi non orientati. Ogni arco $i$ ha un punteggio di passaggio pari a $W_i$ e collega i vertici $U_i$ e $V_i$.

Bob può spostarsi da un vertice all'altro utilizzando gli archi. Bob può usare l'$i$-esimo arco se e solo se il suo punteggio è maggiore o uguale a $W_i$. Può usare lo stesso arco e visitare lo stesso vertice quante volte vuole.

Ogni volta che Bob si trova nel vertice $x$, ha due opzioni per aumentare il proprio punteggio:

• Può ottenere $A_x$ punti gratuitamente. Può usare questa opzione solo una volta durante il suo viaggio.
• Può ottenere $1$ punto per $C_x$ monete. Può usare questa opzione quante volte vuole durante tutto il suo viaggio.

Bob ha ora $Q$ query. Per ogni query $i$, rispondi alla seguente domanda:

• Bob ha un punteggio iniziale pari a $R_i$ e si trova nel vertice $S_i$. Ha intenzione di raggiungere il vertice $T_i$. Qual è il numero minimo di monete necessarie per farlo?

Stampa $-1$ se non può raggiungere il vertice $T_i$ nemmeno con un numero infinito di monete.

Input

• La prima riga contiene un intero $T$ ($1 \le T \le 100$), il numero di casi di test.
• Poi, per ogni caso di test:
  • La prima riga contiene tre interi separati da spazi $N, M, Q$ ($1 \le N, M, Q \le 5 \cdot 10^5$).
  • La seconda riga contiene $N$ interi separati da spazi $A_1, A_2, \dots, A_N$ ($1 \le A_i \le 10^6$).
  • La terza riga contiene $N$ interi separati da spazi $C_1, C_2, \dots, C_N$ ($1 \le C_i \le 10^6$).
  • Seguono poi $M$ righe, ciascuna contenente tre interi separati da spazi $U_i, V_i, W_i$ ($1 \le U_i, V_i \le N; 1 \le W_i \le 10^{12}$).
  • Seguono poi $Q$ righe, ciascuna contenente tre interi separati da spazi $S_i, T_i, R_i$ ($1 \le S_i, T_i \le N; 1 \le R_i \le 10^{12}$).

È garantito che la somma di $N$ su tutti i casi di test non superi $5 \cdot 10^5$.

È garantito che la somma di $M$ su tutti i casi di test non superi $5 \cdot 10^5$.

È garantito che la somma di $Q$ su tutti i casi di test non superi $5 \cdot 10^5$.

Output

Per ogni caso di test, stampa $Q$ righe, ciascuna costituita da un intero, la risposta per quella query.

Esempio

Input di esempio 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

Output di esempio 1

11
0
4
5