給定一個含有 $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