Existe un grafo conexo $G$ que consta de $N$ vértices y $M$ aristas ponderadas no dirigidas. En $G$, el peso de un camino se obtiene mediante la operación XOR de los pesos de todas las aristas en el camino. Tenga en cuenta que está permitido recorrer una misma arista varias veces; en este caso, se realiza la operación XOR del peso tantas veces como se recorra.

Para los vértices $u$ y $v$, sea $d(u, v)$ el peso máximo de un camino desde $u$ hasta $v$.

Usted debe responder $Q$ consultas de la siguiente forma: Dados $l$ y $r$, para todos los $i$ y $j$ tales que $l \le i < j \le r$, encuentre el XOR de los valores de $d(i, j)$.

Entrada

La primera línea contiene tres enteros, $N$, $M$ y $Q$ ($1 \le N, M, Q \le 10^5$).

Cada una de las siguientes $M$ líneas contiene tres enteros, $u$, $v$ y $w$, que describen una arista de peso $w$ que conecta los vértices $u$ y $v$ ($1 \le u, v \le N$, $0 \le w < 2^{30}$). Tenga en cuenta que en esta tarea se permiten múltiples aristas y bucles.

Cada una de las siguientes $Q$ líneas describe una consulta y contiene dos enteros $l$ y $r$ ($1 \le l < r \le N$).

Salida

Para cada consulta, imprima la respuesta en una línea separada.

Ejemplos

Entrada 1

8 10 7
1 2 662784558
3 2 195868257
3 4 294212653
4 5 299265014
6 5 72652580
6 7 29303370
7 8 183954825
2 1 752722885
5 3 197591314
8 4 877461873
4 8
5 7
6 7
2 3
7 8
3 4
2 7

Salida 1

0
713437792
738051848
716356296
736682272
1003204975
987493236