Cho một đồ thị gồm $N$ đỉnh và $M$ cạnh vô hướng. Mỗi cạnh $i$ có hệ số đi qua là $W_i$ và nối hai đỉnh $U_i$ và $V_i$.

Bob được phép di chuyển từ đỉnh này sang đỉnh khác bằng các cạnh. Bob chỉ có thể đi qua cạnh thứ $i$ khi và chỉ khi hệ số của anh ấy lớn hơn hoặc bằng $W_i$. Anh ấy có thể đi qua cùng một cạnh và thăm cùng một đỉnh bao nhiêu lần tùy ý.

Mỗi khi Bob đang ở đỉnh $x$, anh ấy có hai lựa chọn để tăng thêm hệ số:

• Anh ấy có thể nhận thêm $A_x$ hệ số miễn phí. Anh ấy chỉ được sử dụng lựa chọn này tối đa một lần trong suốt hành trình.
• Anh ấy có thể nhận thêm $1$ hệ số với giá $C_x$ đồng xu. Anh ấy có thể sử dụng lựa chọn này bao nhiêu lần tùy ý trong suốt hành trình.

Bob hiện có $Q$ truy vấn. Với mỗi truy vấn $i$, hãy trả lời câu hỏi sau:

• Bob có hệ số ban đầu là $R_i$ và đang ở đỉnh $S_i$. Anh ấy dự định đi đến đỉnh $T_i$. Số lượng đồng xu tối thiểu cần thiết để thực hiện điều này là bao nhiêu?

Hãy in ra $-1$ nếu anh ấy không thể đi đến đỉnh $T_i$ ngay cả khi có vô hạn đồng xu.

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên $T$ ($1 \le T \le 100$), số lượng bộ dữ liệu.
• Tiếp theo, với mỗi bộ dữ liệu:
  • Dòng đầu tiên chứa ba số nguyên cách nhau bởi dấu cách $N, M, Q$ ($1 \le N, M, Q \le 5 \cdot 10^5$).
  • Dòng thứ hai chứa $N$ số nguyên cách nhau bởi dấu cách $A_1, A_2, \dots, A_N$ ($1 \le A_i \le 10^6$).
  • Dòng thứ ba chứa $N$ số nguyên cách nhau bởi dấu cách $C_1, C_2, \dots, C_N$ ($1 \le C_i \le 10^6$).
  • Tiếp theo là $M$ dòng, mỗi dòng chứa ba số nguyên cách nhau bởi dấu cách $U_i, V_i, W_i$ ($1 \le U_i, V_i \le N; 1 \le W_i \le 10^{12}$).
  • Tiếp theo là $Q$ dòng, mỗi dòng chứa ba số nguyên cách nhau bởi dấu cách $S_i, T_i, R_i$ ($1 \le S_i, T_i \le N; 1 \le R_i \le 10^{12}$).

Dữ liệu đảm bảo tổng của $N$ trên tất cả các bộ dữ liệu không vượt quá $5 \cdot 10^5$.

Dữ liệu đảm bảo tổng của $M$ trên tất cả các bộ dữ liệu không vượt quá $5 \cdot 10^5$.

Dữ liệu đảm bảo tổng của $Q$ trên tất cả các bộ dữ liệu không vượt quá $5 \cdot 10^5$.

Kết quả

Với mỗi bộ dữ liệu, in ra $Q$ dòng, mỗi dòng gồm một số nguyên là câu trả lời cho truy vấn tương ứng.

Ví dụ

Ví dụ đầu vào 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

Ví dụ đầu ra 1

11
0
4
5