Se da un grafo con $N$ vértices y $M$ aristas no dirigidas. Cada arista $i$ tiene una clasificación de paso de $W_i$ y conecta los vértices $U_i$ y $V_i$.

A Bob se le permite moverse de un vértice a otro usando las aristas. Bob puede usar la $i$-ésima arista si y solo si su clasificación es mayor o igual que $W_i$. Puede usar la misma arista y visitar el mismo vértice tantas veces como quiera.

Siempre que Bob se encuentre en el vértice $x$, tiene dos opciones para obtener más clasificación:

• Puede obtener $A_x$ de clasificación gratis. Puede usar esta opción solo una vez durante su viaje.
• Puede obtener $1$ de clasificación por $C_x$ monedas. Puede usar esta opción tantas veces como quiera a lo largo de su viaje.

Bob tiene ahora $Q$ consultas. Para cada consulta $i$, responde a la siguiente pregunta:

• Bob tiene una clasificación inicial de $R_i$ y se encuentra en el vértice $S_i$. Planea llegar al vértice $T_i$. ¿Cuál es el número mínimo de monedas necesarias para ello?

Imprime $-1$ si no puede llegar al vértice $T_i$ ni siquiera con un número infinito de monedas.

Entrada

• La primera línea contiene un entero $T$ ($1 \le T \le 100$), el número de casos de prueba.
• Luego, para cada caso de prueba:
  • La primera línea contiene tres enteros separados por espacios $N, M, Q$ ($1 \le N, M, Q \le 5 \cdot 10^5$).
  • La segunda línea contiene $N$ enteros separados por espacios $A_1, A_2, \dots, A_N$ ($1 \le A_i \le 10^6$).
  • La tercera línea contiene $N$ enteros separados por espacios $C_1, C_2, \dots, C_N$ ($1 \le C_i \le 10^6$).
  • A continuación siguen $M$ líneas, cada una con tres enteros separados por espacios $U_i, V_i, W_i$ ($1 \le U_i, V_i \le N; 1 \le W_i \le 10^{12}$).
  • A continuación siguen $Q$ líneas, cada una con tres enteros separados por espacios $S_i, T_i, R_i$ ($1 \le S_i, T_i \le N; 1 \le R_i \le 10^{12}$).

Se garantiza que la suma de $N$ en todos los casos de prueba no supera $5 \cdot 10^5$.

Se garantiza que la suma de $M$ en todos los casos de prueba no supera $5 \cdot 10^5$.

Se garantiza que la suma de $Q$ en todos los casos de prueba no supera $5 \cdot 10^5$.

Salida

Para cada caso de prueba, imprime $Q$ líneas, cada una con un entero, la respuesta para esa consulta.

Ejemplo

Entrada de ejemplo 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

Salida de ejemplo 1

11
0
4
5