Є зв’язний граф $G$ з $N$ вершинами та $M$ зваженими неорієнтованими ребрами. У $G$ вага шляху дорівнює побітовому XOR ваг усіх його ребер. Зауважте, що одним ребром дозволено проходити кілька разів; у такому разі його вага включається в XOR відповідну кількість разів.

Для вершин $u$ та $v$ нехай $d(u, v)$ — найбільша вага шляху від $u$ до $v$.

Потрібно відповісти на $Q$ запитів такого вигляду:

Для заданих $l$ та $r$ знайдіть XOR значень $d(i, j)$ за всіма $i$ та $j$, для яких $l \le i < j \le r$.

Вхідні дані

Перший рядок містить три цілі числа $N$, $M$ та $Q$ ($1 \le N, M, Q \le 10^5$).

Кожен із наступних $M$ рядків містить три цілі числа $u$, $v$ та $w$, що описують ребро ваги $w$ між вершинами $u$ та $v$ ($1 \le u, v \le N$, $0 \le w < 2^{30}$). Зауважте, що в цій задачі дозволено кратні ребра та петлі.

Кожен із наступних $Q$ рядків описує один запит і містить два цілі числа $l$ та $r$ ($1 \le l < r \le N$).

Вихідні дані

Для кожного запиту виведіть відповідь в окремому рядку.

Приклади

Вхідні дані 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

Вихідні дані 1

0
713437792
738051848
716356296
736682272
1003204975
987493236