Gitt en graf med $N$ noder og $M$ urettede kanter. Hver kant $i$ har en passeringsrating på $W_i$ og forbinder nodene $U_i$ og $V_i$.

Bob har lov til å bevege seg fra én node til en annen ved hjelp av kanter. Bob kan bruke den $i$-te kanten hvis og bare hvis ratingen hans er større enn eller lik $W_i$. Han kan bruke samme kant og besøke samme node så mange ganger han vil.

Hver gang Bob befinner seg i node $x$, har han to alternativer for å få ny rating:

• Han kan få $A_x$ i rating gratis. Han kan bruke dette alternativet bare én gang i løpet av reisen sin.
• Han kan få $1$ i rating for $C_x$ mynter. Han kan bruke dette alternativet så mange ganger han vil gjennom hele reisen sin.

Bob har nå $Q$ spørringer. For hver spørring $i$, svar på følgende spørsmål:

• Bob har en startrating på $R_i$ og befinner seg i node $S_i$. Han planlegger å nå node $T_i$. Hva er det minimale antallet mynter som kreves for dette?

Skriv ut $-1$ hvis han ikke kan nå node $T_i$ selv med et uendelig antall mynter.

Inndata

• Den første linjen inneholder ett heltall $T$ ($1 \le T \le 100$), antallet testtilfeller.
• Deretter, for hvert testtilfelle:
  • Den første linjen inneholder tre mellomromseparerte heltall $N, M, Q$ ($1 \le N, M, Q \le 5 \cdot 10^5$).
  • Den andre linjen inneholder $N$ mellomromseparerte heltall $A_1, A_2, \dots, A_N$ ($1 \le A_i \le 10^6$).
  • Den tredje linjen inneholder $N$ mellomromseparerte heltall $C_1, C_2, \dots, C_N$ ($1 \le C_i \le 10^6$).
  • Deretter følger $M$ linjer, som hver inneholder tre mellomromseparerte heltall $U_i, V_i, W_i$ ($1 \le U_i, V_i \le N; 1 \le W_i \le 10^{12}$).
  • Deretter følger $Q$ linjer, som hver inneholder tre mellomromseparerte heltall $S_i, T_i, R_i$ ($1 \le S_i, T_i \le N; 1 \le R_i \le 10^{12}$).

Det er garantert at summen av $N$ over alle testtilfeller ikke overstiger $5 \cdot 10^5$.

Det er garantert at summen av $M$ over alle testtilfeller ikke overstiger $5 \cdot 10^5$.

Det er garantert at summen av $Q$ over alle testtilfeller ikke overstiger $5 \cdot 10^5$.

Utdata

For hvert testtilfelle skal du skrive ut $Q$ linjer, som hver består av ett heltall, svaret på den spørringen.

Eksempel

Eksempelinndata 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

Eksempelutdata 1

11
0
4
5