Annettuna on verkko, jossa on $N$ solmua ja $M$ suuntaamatonta kaarta. Jokaisella kaarella $i$ on läpikulkuluokitus $W_i$, ja se yhdistää solmut $U_i$ ja $V_i$.

Bob saa liikkua solmusta toiseen kaaria pitkin. Bob voi käyttää $i$:ttä kaarta, jos ja vain jos hänen luokituksensa on suurempi tai yhtä suuri kuin $W_i$. Hän voi käyttää samaa kaarta ja vierailla samassa solmussa niin monta kertaa kuin haluaa.

Aina kun Bob on solmussa $x$, hänellä on kaksi vaihtoehtoa hankkia lisää luokitusta:

• Hän voi saada $A_x$ luokitusta ilmaiseksi. Hän voi käyttää tätä vaihtoehtoa vain kerran matkansa aikana.
• Hän voi saada $1$ luokitusta $C_x$ kolikolla. Hän voi käyttää tätä vaihtoehtoa niin monta kertaa kuin haluaa koko matkansa ajan.

Bobilla on nyt $Q$ kyselyä. Vastaa jokaisen kyselyn $i$ kohdalla seuraavaan kysymykseen:

• Bobin alkuluokitus on $R_i$ ja hän on solmussa $S_i$. Hän aikoo päästä solmuun $T_i$. Mikä on tähän tarvittava pienin mahdollinen kolikoiden määrä?

Tulosta $-1$, jos hän ei voi päästä solmuun $T_i$ edes äärettömällä määrällä kolikoita.

Syöte

• Ensimmäinen rivi sisältää yhden kokonaisluvun $T$ ($1 \le T \le 100$), testitapausten lukumäärän.
• Tämän jälkeen jokaiselle testitapaukselle:
  • Ensimmäinen rivi sisältää kolme välilyönnein erotettua kokonaislukua $N, M, Q$ ($1 \le N, M, Q \le 5 \cdot 10^5$).
  • Toinen rivi sisältää $N$ välilyönnein erotettua kokonaislukua $A_1, A_2, \dots, A_N$ ($1 \le A_i \le 10^6$).
  • Kolmas rivi sisältää $N$ välilyönnein erotettua kokonaislukua $C_1, C_2, \dots, C_N$ ($1 \le C_i \le 10^6$).
  • Seuraavaksi tulee $M$ riviä, joista jokainen sisältää kolme välilyönnein erotettua kokonaislukua $U_i, V_i, W_i$ ($1 \le U_i, V_i \le N; 1 \le W_i \le 10^{12}$).
  • Seuraavaksi tulee $Q$ riviä, joista jokainen sisältää kolme välilyönnein erotettua kokonaislukua $S_i, T_i, R_i$ ($1 \le S_i, T_i \le N; 1 \le R_i \le 10^{12}$).

On taattu, että lukujen $N$ summa yli kaikkien testitapausten ei ylitä arvoa $5 \cdot 10^5$.

On taattu, että lukujen $M$ summa yli kaikkien testitapausten ei ylitä arvoa $5 \cdot 10^5$.

On taattu, että lukujen $Q$ summa yli kaikkien testitapausten ei ylitä arvoa $5 \cdot 10^5$.

Tuloste

Tulosta jokaiselle testitapaukselle $Q$ riviä, joista jokainen koostuu yhdestä kokonaisluvusta, vastauksesta kyseiseen kyselyyn.

Esimerkki

Esimerkkisyöte 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

Esimerkkituloste 1

11
0
4
5