408078: GYM102979 F Find the XOR

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 < j \leq r$$$, find the XOR of the values of $$$d (i, j)$$$.

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 < 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 < r \leq N$$$).

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

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

0
713437792
738051848
716356296
736682272
1003204975
987493236