Es gibt einen zusammenhängenden Graphen $G$ mit $N$ Knoten und $M$ gewichteten ungerichteten Kanten. In $G$ erhält man das Gewicht eines Weges, indem man die Gewichte aller Kanten des Weges bitweise mit XOR verknüpft. Eine Kante darf mehrfach durchlaufen werden; in diesem Fall geht ihr Gewicht entsprechend oft in die XOR-Verknüpfung ein.

Für die Knoten $u$ und $v$ sei $d(u,v)$ das maximale Gewicht eines Weges von $u$ nach $v$.

Du musst $Q$ Anfragen der folgenden Form beantworten:

Gegeben sind $l$ und $r$. Bestimme das XOR aller Werte $d(i,j)$ für alle $i,j$ mit $l\le i<j\le r$.

Eingabe

Die erste Zeile enthält drei Ganzzahlen $N,M,Q$ ($1\le N,M,Q\le10^5$).

Jede der folgenden $M$ Zeilen enthält drei Ganzzahlen $u,v,w$ und beschreibt eine Kante mit Gewicht $w$ zwischen den Knoten $u$ und $v$ ($1\le u,v\le N$, $0\le w<2^{30}$). Beachte, dass Mehrfachkanten und Schleifen in dieser Aufgabe erlaubt sind.

Jede der folgenden $Q$ Zeilen beschreibt eine Anfrage und enthält zwei Ganzzahlen $l$ und $r$ ($1\le l<r\le N$).

Ausgabe

Gib für jede Anfrage die Antwort in einer eigenen Zeile aus.

Beispiele

Eingabe 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

Ausgabe 1

0
713437792
738051848
716356296
736682272
1003204975
987493236