408078: GYM102979 F Find the XOR
Description
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)$$$.
InputThe 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$$$).
OutputFor each query, print the answer on a separate line.
ExampleInput8 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 7Output
0 713437792 738051848 716356296 736682272 1003204975 987493236