Al igual que muchas cosas en el mundo, el título de este problema no tiene ningún significado.

Dado un grafo no dirigido con $n$ vértices y $m$ aristas, las aristas están numeradas de $1$ a $m$ en orden, y cada arista tiene un peso $c_i$. Ahora debes responder $q$ consultas, cada una con la siguiente forma:

• Si solo se conservan las aristas con índices en $[l, r]$, ¿cuál es la suma de los pesos de todas las aristas puente en el grafo módulo $2^{64}$?

Debes responder a cada consulta.

Quizás quieras conocer la definición de puente: una arista se llama puente si y solo si al eliminarla aumenta el número de componentes conexas del grafo.

Entrada

La primera línea contiene $n, m, q$ ($1 \le n \le 500$, $1 \le m, q \le 10^5$), que representan el número de vértices, aristas y consultas en el grafo.

Las siguientes $m$ líneas contienen cada una tres enteros $u, v, c$ ($1 \le u, v \le n$, $0 \le c < 2^{64}$), que representan una arista en el grafo.

Las siguientes $q$ líneas contienen cada una dos enteros positivos $l, r$ ($1 \le l \le r \le m$), que representan una consulta.

Se garantiza que el grafo no contiene bucles, pero puede contener aristas múltiples.

Salida

Para cada consulta, imprime una línea con un entero que represente la respuesta.

Ejemplo

Entrada 1

5 6 6
1 2 1
2 3 2
2 4 4
2 5 8
1 3 16
4 5 32
1 3
2 4
3 5
4 6
2 6
1 6

Salida 1

7
14
28
56
18
0