Kleptocrat

Your company has a policy that refunds every employee an amount proportional to the shortest distance between their home and their office. This creates the loophole that many employees deliberately move very far away to claim the largest possible reimbursement.

One employee has abused this policy far too much and is about to bankrupt you. You have to stop this before you cancel the policy next year. The rules are strict, though: as long as the employee keeps track of the distances they have travelled, you are forced to reimburse them.

Then you have a flash of inspiration. Nowhere does it say you have to use Euclidean distances! You start working on subtler distance functions, and now you have a first prototype: XOR distance. The length of a path is the XOR of the lengths of the edges on the path, not the sum. The distance between two locations is the length of the shortest path between them.

You want to test this principle on the transport network, for the location of each of your employees in turn.

• The first line contains three integers $n$ ($2 \leq n \leq 10^4$), $m$ ($n-1 \leq m \leq 10^5$), and $q$ (${1 \leq q \leq 10^5}$): the number of nodes, edges, and questions.
• The next $m$ lines describe the edges. Each line contains three integers $x$, $y$, $w$ ($1 \leq x,y \leq n$, $x\neq y$, $0 \leq w \leq 10^{18}$), meaning there is an undirected edge of length $w$ between nodes $x$ and $y$.
• The next $q$ lines describe the questions. Each line contains two integers $a$, $b$ ($1 \leq a,b \leq n$), asking for the shortest distance between nodes $a$ and $b$.

Between every pair of distinct nodes there is at most one edge, and every node is reachable from every other node.

For each question, output the shortest distance between nodes $a$ and $b$ on its own line.