Дан связный граф $G$, состоящий из $N$ вершин и $M$ взвешенных неориентированных ребер. В графе $G$ вес пути определяется как XOR-сумма весов всех ребер, входящих в этот путь. Обратите внимание, что разрешается проходить по одному и тому же ребру несколько раз; в этом случае вес ребра учитывается в XOR-сумме соответствующее количество раз.

Для вершин $u$ и $v$ обозначим через $d(u, v)$ максимальный вес пути из $u$ в $v$.

Вам необходимо ответить на $Q$ запросов следующего вида: Даны $l$ и $r$, для всех пар $i$ и $j$ таких, что $l \le i < j \le r$, найдите XOR-сумму значений $d(i, j)$.

Входные данные

Первая строка содержит три целых числа $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