Diberikan sebuah graf dengan $N$ simpul dan $M$ sisi tak berarah. Setiap sisi $i$ memiliki rating lewat sebesar $W_i$ dan menghubungkan simpul $U_i$ dan $V_i$.

Bob diperbolehkan berpindah dari satu simpul ke simpul lainnya menggunakan sisi. Bob dapat menggunakan sisi ke-$i$ jika dan hanya jika rating miliknya lebih besar dari atau sama dengan $W_i$. Ia dapat menggunakan sisi yang sama dan mengunjungi simpul yang sama sebanyak yang ia inginkan.

Setiap kali Bob berada di simpul $x$, ia memiliki dua pilihan untuk mendapatkan rating baru:

• Ia dapat memperoleh $A_x$ rating secara gratis. Ia hanya dapat menggunakan pilihan ini satu kali selama perjalanannya.
• Ia dapat memperoleh $1$ rating dengan biaya $C_x$ koin. Ia dapat menggunakan pilihan ini sebanyak yang ia inginkan sepanjang perjalanannya.

Bob sekarang memiliki $Q$ kueri. Untuk setiap kueri $i$, jawablah pertanyaan berikut:

• Bob memiliki rating awal sebesar $R_i$ dan berada di simpul $S_i$. Ia berencana untuk mencapai simpul $T_i$. Berapakah jumlah koin minimum yang diperlukan untuk ini?

Cetak $-1$ jika ia tidak dapat mencapai simpul $T_i$ meskipun dengan jumlah koin yang tak terbatas.

Masukan

• Baris pertama berisi satu bilangan bulat $T$ ($1 \le T \le 100$), jumlah kasus uji.
• Kemudian, untuk setiap kasus uji:
  • Baris pertama berisi tiga bilangan bulat yang dipisahkan spasi $N, M, Q$ ($1 \le N, M, Q \le 5 \cdot 10^5$).
  • Baris kedua berisi $N$ bilangan bulat yang dipisahkan spasi $A_1, A_2, \dots, A_N$ ($1 \le A_i \le 10^6$).
  • Baris ketiga berisi $N$ bilangan bulat yang dipisahkan spasi $C_1, C_2, \dots, C_N$ ($1 \le C_i \le 10^6$).
  • Kemudian, diikuti oleh $M$ baris, masing-masing berisi tiga bilangan bulat yang dipisahkan spasi $U_i, V_i, W_i$ ($1 \le U_i, V_i \le N; 1 \le W_i \le 10^{12}$).
  • Kemudian, diikuti oleh $Q$ baris, masing-masing berisi tiga bilangan bulat yang dipisahkan spasi $S_i, T_i, R_i$ ($1 \le S_i, T_i \le N; 1 \le R_i \le 10^{12}$).

Dijamin bahwa jumlah dari $N$ di seluruh kasus uji tidak melebihi $5 \cdot 10^5$.

Dijamin bahwa jumlah dari $M$ di seluruh kasus uji tidak melebihi $5 \cdot 10^5$.

Dijamin bahwa jumlah dari $Q$ di seluruh kasus uji tidak melebihi $5 \cdot 10^5$.

Keluaran

Untuk setiap kasus uji, cetak $Q$ baris, masing-masing terdiri dari satu bilangan bulat, yaitu jawaban untuk kueri tersebut.

Contoh

Contoh Masukan 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

Contoh Keluaran 1

11
0
4
5