F. Find the XOR
time limit per test
2 seconds
memory limit per test
1024 mebibytes
input
standard input
output
standard output

There is a connected graph $$$G$$$ consisting of $$$N$$$ vertices and $$$M$$$ weighted undirected edges. In $$$G$$$, the weight of the path is obtained by XORing the weights of all edges in the path. Note that it is allowed to walk along one edge multiple times, in this case, you are XORing the weight that number of times.

For vertices $$$u$$$ and $$$v$$$, let $$$d (u, v)$$$ be the maximum weight of a path from $$$u$$$ to $$$v$$$.

You need to answer $$$Q$$$ queries of the following form:

Given $$$l$$$ and $$$r$$$, for all $$$i$$$ and $$$j$$$ such as $$$l \leq i \lt j \leq r$$$, find the XOR of the values of $$$d (i, j)$$$.

Input

The first line contains three integers, $$$N$$$, $$$M$$$, and $$$Q$$$ ($$$1 \leq N, M, Q \leq 10^5$$$).

Each of the following $$$M$$$ lines contains three integers, $$$u$$$, $$$v$$$, and $$$w$$$, describing an edge of weight $$$w$$$ connecting vertices $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le N$$$, $$$0 \le w \lt 2^{30}$$$). Note that multiple edges and loops are allowed in this task.

Each of the following $$$Q$$$ lines describes one query and contains two integers $$$l$$$ and $$$r$$$ ($$$1 \leq l \lt r \leq N$$$).

Output

For each query, print the answer on a separate line.

Example
Input
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
Output
0
713437792
738051848
716356296
736682272
1003204975
987493236