Colindăm Doamne colind

Colindăm Doamne colind
Being lost in the mountains of Valea Jiului, Nicolae found one of the best problems he had seen. Upon reading it, he was filled with joy and started singing the beautiful ancient carol from above. Now he wants to share his discovery with you.

You are given an undirected connected weighted graph with $N$ nodes and $M$ edges. The graph is a cactus (i.e. each node is part of at most one cycle).

A trail in this graph is defined as a sequence of nodes $a_1, a_2, a_3, \dots, a_k$ such that there exists an edge between $a_i$ and $a_{i+1}$ ($1 \le i \le k-1$) and no edge is traversed more than once (note that nodes can be traversed more than once).

The cost of such a trail is the XOR of all the edges belonging to the trail.

Task

For $Q$ pairs of nodes $(u,v)$ you have to find the minimum cost of a trail that starts at $u$ and ends in $v$.

Input data

The first line contains the numbers $N$, $M$ and $Q$.

The next $M$ lines each contain 3 integers $a$, $b$ and $c$, meaning there is an edge between $a$ and $b$ with cost $c$.

The next $Q$ lines each contain 2 integers $u$ and $v$, meaning a query with endpoints in $u$ and $v$.

Output data

The output should contain $Q$ lines, the $i$-th line containing the answer for the $i$-th query.

Constraints and clarifications

• $1 \le N, Q \le 10^5$
• $N-1 \le M \le 2 \cdot 10^5$
• The cost of any edge is at least $0$ and strictly smaller than $2^{30}$.
• The input graph does not contain multiple edges or self loops.

Example

stdin

10 11 10
10 1 226113825
1 6 646080092
7 9 363375133
8 2 412692880
4 7 493985477
5 1 616172447
7 2 313111157
4 2 256007221
3 1 814516487
2 1 627361906
10 6 549967887
6 8
10 2
2 9
7 10
9 3
1 4
9 6
2 2
4 5
2 9

stdout

272636108
589395489
117512296
823309521
309537176
555291445
75351747
0
87648303
117512296