Задано граф із $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