$N$ 個の頂点と $M$ 本の無向辺からなるグラフが与えられます。各辺 $i$ には通行レーティング $W_i$ が設定されており、頂点 $U_i$ と頂点 $V_i$ を結んでいます。

Bob は辺を使ってある頂点から別の頂点へ移動することができます。Bob は自身のレーティングが $W_i$ 以上であるとき、かつそのときに限り $i$ 番目の辺を通ることができます。また、同じ辺を何度使っても、同じ頂点を何度訪れても構いません。

Bob は頂点 $x$ にいるとき、いつでも以下の 2 つの選択肢によって自身のレーティングを増やすことができます：

• 無料でレーティングを $A_x$ 増やす。この選択肢は旅全体を通して高々 1 回しか使用できない。
• $C_x$ 枚のコインを支払ってレーティングを $1$ 増やす。この選択肢は旅全体を通して何回でも使用できる。

Bob には $Q$ 個のクエリがあります。各クエリ $i$ について、次の質問に答えてください：

• Bob の初期レーティングは $R_i$ であり、頂点 $S_i$ にいます。彼は頂点 $T_i$ に到達しようとしています。このために必要なコインの最小枚数はいくらですか？

無限にコインを持っていたとしても頂点 $T_i$ に到達できない場合は $-1$ を出力してください。

入力

• 1 行目には、テストケースの数を表す 1 つの整数 $T$（$1 \le T \le 100$）が含まれます。
• その後、各テストケースについて：
  • 1 行目には、空白で区切られた 3 つの整数 $N, M, Q$（$1 \le N, M, Q \le 5 \cdot 10^5$）が含まれます。
  • 2 行目には、空白で区切られた $N$ 個の整数 $A_1, A_2, \dots, A_N$（$1 \le A_i \le 10^6$）が含まれます。
  • 3 行目には、空白で区切られた $N$ 個の整数 $C_1, C_2, \dots, C_N$（$1 \le C_i \le 10^6$）が含まれます。
  • 続く $M$ 行には、それぞれ空白で区切られた 3 つの整数 $U_i, V_i, W_i$（$1 \le U_i, V_i \le N; 1 \le W_i \le 10^{12}$）が含まれます。
  • 続く $Q$ 行には、それぞれ空白で区切られた 3 つの整数 $S_i, T_i, R_i$（$1 \le S_i, T_i \le N; 1 \le R_i \le 10^{12}$）が含まれます。

すべてのテストケースにわたる $N$ の総和は $5 \cdot 10^5$ を超えないことが保証されています。

すべてのテストケースにわたる $M$ の総和は $5 \cdot 10^5$ を超えないことが保証されています。

すべてのテストケースにわたる $Q$ の総和は $5 \cdot 10^5$ を超えないことが保証されています。

出力

各テストケースについて、対応するクエリの答えである 1 つの整数からなる行を $Q$ 行出力してください。

出力例・入力例

入力例 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

出力例 1

11
0
4
5