给定一个含有 $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