Dany jest spójny graf $G$ składający się z $N$ wierzchołów i $M$ ważonych krawędzi nieskierowanych. W grafie $G$ wagę ścieżki otrzymuje się poprzez wykonanie operacji XOR na wagach wszystkich krawędzi wchodzących w skład ścieżki. Zauważ, że dozwolone jest wielokrotne przechodzenie przez tę samą krawędź; w takim przypadku wagę krawędzi należy uwzględnić w operacji XOR tyle razy, ile razy została ona użyta.

Dla wierzchołków $u$ oraz $v$, niech $d(u, v)$ oznacza maksymalną wagę ścieżki z $u$ do $v$.

Musisz odpowiedzieć na $Q$ zapytań następującej postaci: Mając dane $l$ oraz $r$, dla wszystkich $i$ oraz $j$ takich, że $l \le i < j \le r$, oblicz XOR wartości $d(i, j)$.

Wejście

W pierwszej linii znajdują się trzy liczby całkowite $N$, $M$ oraz $Q$ ($1 \le N, M, Q \le 10^5$).

Każda z kolejnych $M$ linii zawiera trzy liczby całkowite $u$, $v$ oraz $w$, opisujące krawędź o wadze $w$ łączącą wierzchołki $u$ oraz $v$ ($1 \le u, v \le N$, $0 \le w < 2^{30}$). Zauważ, że w tym zadaniu dozwolone są krawędzie wielokrotne oraz pętle.

Każda z kolejnych $Q$ linii opisuje jedno zapytanie i zawiera dwie liczby całkowite $l$ oraz $r$ ($1 \le l < r \le N$).

Wyjście

Dla każdego zapytania wypisz wynik w osobnej linii.

Przykład

Wejście 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

Wyjście 1

0
713437792
738051848
716356296
736682272
1003204975
987493236