Soit un graphe connexe $G$ composé de $N$ sommets et $M$ arêtes pondérées non orientées. Dans $G$, le poids d'un chemin est obtenu en effectuant le XOR des poids de toutes les arêtes du chemin. Notez qu'il est permis de parcourir une même arête plusieurs fois ; dans ce cas, vous effectuez le XOR du poids autant de fois que l'arête est parcourue.

Pour des sommets $u$ et $v$, soit $d(u, v)$ le poids maximum d'un chemin allant de $u$ à $v$.

Vous devez répondre à $Q$ requêtes de la forme suivante : Étant donné $l$ et $r$, pour tous $i$ et $j$ tels que $l \le i < j \le r$, calculez le XOR des valeurs de $d(i, j)$.

Entrée

La première ligne contient trois entiers, $N$, $M$ et $Q$ ($1 \le N, M, Q \le 10^5$).

Chacune des $M$ lignes suivantes contient trois entiers, $u$, $v$ et $w$, décrivant une arête de poids $w$ reliant les sommets $u$ et $v$ ($1 \le u, v \le N$, $0 \le w < 2^{30}$). Notez que les arêtes multiples et les boucles sont autorisées dans ce problème.

Chacune des $Q$ lignes suivantes décrit une requête et contient deux entiers $l$ et $r$ ($1 \le l < r \le N$).

Sortie

Pour chaque requête, affichez la réponse sur une ligne séparée.

Exemples

Entrée 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

Sortie 1

0
713437792
738051848
716356296
736682272
1003204975
987493236