Дан граф с $N$ вершинами и $M$ неориентированными рёбрами. Каждое ребро $i$ имеет проходной рейтинг $W_i$ и соединяет вершины $U_i$ и $V_i$.

Боб может перемещаться из одной вершины в другую по рёбрам. Боб может пройти по $i$-му ребру тогда и только тогда, когда его рейтинг больше или равен $W_i$. Он может проходить по одному и тому же ребру и посещать одну и ту же вершину сколько угодно раз.

Всякий раз, когда Боб находится в вершине $x$, у него есть два способа повысить свой рейтинг:

• Он может бесплатно увеличить рейтинг на $A_x$. Этим способом он может воспользоваться не более одного раза за всё время путешествия.
• Он может увеличить рейтинг на $1$ за $C_x$ монет. Этим способом он может пользоваться сколько угодно раз на протяжении всего путешествия.

Теперь у Боба есть $Q$ запросов. Для каждого запроса $i$ ответьте на следующий вопрос:

• Начальный рейтинг Боба равен $R_i$, и он находится в вершине $S_i$. Он планирует добраться до вершины $T_i$. Какое минимальное количество монет для этого потребуется?

Выведите $-1$, если он не сможет добраться до вершины $T_i$ даже при наличии бесконечного количества монет.

Входные данные

• Первая строка содержит одно целое число $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