畀定一個有 $N$ 個頂點同 $M$ 條無向邊嘅圖。每條邊 $i$ 都有一個通行評分 $W_i$，並連接頂點 $U_i$ 同 $V_i$。

Bob 可以利用呢啲邊由一個頂點移動去另一個頂點。當且僅當 Bob 嘅評分大於或等於 $W_i$ 嗰陣，佢先至可以用第 $i$ 條邊。佢可以隨意多次使用同一條邊同埋訪問同一個頂點。

每當 Bob 位於頂點 $x$ 嗰陣，佢有兩個提升評分嘅選擇：

• 佢可以免費獲得 $A_x$ 點評分。喺成個旅程入面，佢只可以使用呢個選擇一次。
• 佢可以花費 $C_x$ 個金幣獲得 $1$ 點評分。喺成個旅程入面，佢可以無限次使用呢個選擇。

Bob 而家有 $Q$ 個詢問。對於每個詢問 $i$，請回答以下問題：

• Bob 嘅初始評分為 $R_i$，而且位於頂點 $S_i$。佢計劃到達頂點 $T_i$。為此最少需要幾多個金幣？

如果就算有無限個金幣佢都去唔到頂點 $T_i$，請輸出 $-1$。

輸入格式

• 第一行包含一個整數 $T$（$1 \le T \le 100$），表示測試用例嘅數量。
• 對於每個測試用例：
  • 第一行包含三個用空格分隔嘅整數 $N, M, Q$（$1 \le N, M, Q \le 5 \cdot 10^5$）。
  • 第二行包含 $N$ 個用空格分隔嘅整數 $A_1, A_2, \dots, A_N$（$1 \le A_i \le 10^6$）。
  • 第三行包含 $N$ 個用空格分隔嘅整數 $C_1, C_2, \dots, C_N$（$1 \le C_i \le 10^6$）。
  • 接落嚟有 $M$ 行，每行包含三個用空格分隔嘅整數 $U_i, V_i, W_i$（$1 \le U_i, V_i \le N; 1 \le W_i \le 10^{12}$）。
  • 接落嚟有 $Q$ 行，每行包含三個用空格分隔嘅整數 $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$。

輸出格式

對於每個測試用例，輸出 $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