Há um grafo conexo $G$ composto por $N$ vértices e $M$ arestas ponderadas não direcionadas. Em $G$, o peso de um caminho é obtido aplicando XOR aos pesos de todas as arestas do caminho. Note que é permitido percorrer a mesma aresta várias vezes; nesse caso, o seu peso participa no XOR esse número de vezes.

Para os vértices $u$ e $v$, seja $d(u, v)$ o maior peso de um caminho de $u$ a $v$.

Deve responder a $Q$ consultas da forma seguinte:

Dados $l$ e $r$, encontre o XOR dos valores de $d(i, j)$ para todos os $i$ e $j$ tais que $l \le i < j \le r$.

Entrada

A primeira linha contém três inteiros $N$, $M$ e $Q$ ($1 \le N, M, Q \le 10^5$).

Cada uma das $M$ linhas seguintes contém três inteiros $u$, $v$ e $w$, que descrevem uma aresta de peso $w$ ligando os vértices $u$ e $v$ ($1 \le u, v \le N$, $0 \le w < 2^{30}$). Note que são permitidas arestas múltiplas e laços neste problema.

Cada uma das $Q$ linhas seguintes descreve uma consulta e contém dois inteiros $l$ e $r$ ($1 \le l < r \le N$).

Saída

Para cada consulta, imprima a resposta numa linha separada.

Exemplos

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

Saída 1

0
713437792
738051848
716356296
736682272
1003204975
987493236