Given a graph with $N$ vertices and $M$ unordered edges. Each edge $i$ has a passing rating of $W_i$ and connects vertices $U_i$ and $V_i$.

Bob is allowed to move from one vertex to another using edges. Bob can use the $i$-th edge if and only if his rating is greater than or equal to $W_i$. He can use the same edge and visit the same vertex as many times as he wants.

Whenever Bob is located at vertex $x$, he has two options for gaining a new rating:

• He can gain $A_x$ rating for free. He can use this option only once during his journey.
• He can gain $1$ rating for $C_x$ coins. He can use this option as many times as he wants throughout his journey.

Bob now has $Q$ queries. For each query $i$, answer the following question:

• Bob has an initial rating of $R_i$ and is located at vertex $S_i$. He is planning to reach vertex $T_i$. What is the minimum number of coins required for this?

Print $-1$ if he cannot reach vertex $T_i$ even with an infinite number of coins.

Input

• The first line contains one integer $T$ ($1 \le T \le 100$), the number of test cases.
• Then, for each test case:
  • The first line contains three space-separated integers $N, M, Q$ ($1 \le N, M, Q \le 5 \cdot 10^5$).
  • The second line contains $N$ space-separated integers $A_1, A_2, \dots, A_N$ ($1 \le A_i \le 10^6$).
  • The third line contains $N$ space-separated integers $C_1, C_2, \dots, C_N$ ($1 \le C_i \le 10^6$).
  • Then, $M$ lines follow, each containing three space-separated integers $U_i, V_i, W_i$ ($1 \le U_i, V_i \le N; 1 \le W_i \le 10^{12}$).
  • Then, $Q$ lines follow, each containing three space-separated integers $S_i, T_i, R_i$ ($1 \le S_i, T_i \le N; 1 \le R_i \le 10^{12}$).

It is guaranteed that the sum of $N$ across all test cases does not exceed $5 \cdot 10^5$.

It is guaranteed that the sum of $M$ across all test cases does not exceed $5 \cdot 10^5$.

It is guaranteed that the sum of $Q$ across all test cases does not exceed $5 \cdot 10^5$.

Output

For each test case, print $Q$ lines, each consisting of one integer, the answer for that query.

Example

Sample Input 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

Sample Output 1

11
0
4
5