Givet är en graf med $N$ hörn och $M$ oriktade kanter. Varje kant $i$ har en passeringsranking på $W_i$ och förbinder hörnen $U_i$ och $V_i$.

Bob får förflytta sig från ett hörn till ett annat med hjälp av kanter. Bob kan använda den $i$-te kanten om och endast om hans ranking är större än eller lika med $W_i$. Han kan använda samma kant och besöka samma hörn hur många gånger han vill.

Närhelst Bob befinner sig vid hörn $x$ har han två alternativ för att skaffa ny ranking:

• Han kan få $A_x$ i ranking gratis. Han kan använda detta alternativ endast en gång under sin resa.
• Han kan få $1$ i ranking för $C_x$ mynt. Han kan använda detta alternativ hur många gånger han vill under hela sin resa.

Bob har nu $Q$ frågor. För varje fråga $i$, svara på följande:

• Bob har en startranking på $R_i$ och befinner sig vid hörn $S_i$. Han planerar att nå hörn $T_i$. Vilket är det minsta antalet mynt som krävs för detta?

Skriv ut $-1$ om han inte kan nå hörn $T_i$ ens med ett oändligt antal mynt.

Indata

• Den första raden innehåller ett heltal $T$ ($1 \le T \le 100$), antalet testfall.
• Därefter, för varje testfall:
  • Den första raden innehåller tre mellanslagsseparerade heltal $N, M, Q$ ($1 \le N, M, Q \le 5 \cdot 10^5$).
  • Den andra raden innehåller $N$ mellanslagsseparerade heltal $A_1, A_2, \dots, A_N$ ($1 \le A_i \le 10^6$).
  • Den tredje raden innehåller $N$ mellanslagsseparerade heltal $C_1, C_2, \dots, C_N$ ($1 \le C_i \le 10^6$).
  • Därefter följer $M$ rader som var och en innehåller tre mellanslagsseparerade heltal $U_i, V_i, W_i$ ($1 \le U_i, V_i \le N; 1 \le W_i \le 10^{12}$).
  • Därefter följer $Q$ rader som var och en innehåller tre mellanslagsseparerade heltal $S_i, T_i, R_i$ ($1 \le S_i, T_i \le N; 1 \le R_i \le 10^{12}$).

Det garanteras att summan av $N$ över alla testfall inte överstiger $5 \cdot 10^5$.

Det garanteras att summan av $M$ över alla testfall inte överstiger $5 \cdot 10^5$.

Det garanteras att summan av $Q$ över alla testfall inte överstiger $5 \cdot 10^5$.

Utdata

För varje testfall, skriv ut $Q$ rader som var och en består av ett heltal, svaret på den frågan.

Exempel

Exempelindata 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

Exempelutdata 1

11
0
4
5