A tree is a strange type of graph. We will not be dealing with trees today, as they are too hard.
You are instead given a graph of 
~N~ nodes and 
~M~ edges. Edge 
~i~ connects nodes 
~u_i~ and 
~v_i~ with a value of 
~k_i~. A path from 
~a_j~ to 
~b_j~ consists of a sequence of the ~M~ edges, such that consecutive edges in the path share a common node. The value of this path is the bitwise OR of all the edge values in the path.
Given 
~Q~ queries, 
~a_j, b_j~, can you determine the minimum path value of a path from ~a_j~ to ~b_j~?
Input Specification
The first line will contain three integers 
~N, M, Q~ 
~(2 \le N \le 5 \times 10^4, N-1 \le M \le 10^5, 1 \le Q \le 10^5)~.
The next ~M~ lines will each contain three integers, 
~u_i, v_i, k_i~ 
~(1 \le u_i, v_i \le N, u_i \neq v_i, 0 \le k_i \le 100)~, indicating there is an edge between nodes ~u_i~ and ~v_i~ of value ~k_i~. Note that there may be duplicate edges between nodes. It is guaranteed that the entire graph is connected.
The next ~Q~ lines will each contain two integers, ~a_j, b_j~ 
~(1 \le a_j, b_j \le N, a_j \neq b_j)~.
Output Specification
For each query, output one integer, the minimum path value.
Subtasks
For 2/15 of the points, 
~k_i \le 1, N \le 10, M \le 20~.
For an additional 3/15 of the points, 
~k_i \le 1~.
Sample Input 1
3 4 2
1 2 1
2 3 1
1 3 0
2 3 0
1 3
1 2
Sample Output 1
0
0
Note: You do not need to pass sample 2 for subtask 1 or 2.
Sample Input 2
4 5 5
1 3 3
1 2 2
2 3 1
3 4 4
2 4 1
1 3
1 4
3 4
2 3
1 2
Sample Output 2
3
3
1
1
2
Comments
What's the point of k?
Edit: Nvm, I just read the text again and yeah.
I might just be stupid, but in the second sample input, if I have calculated correctly, the value of the path should be 2 but it actually shows 1. I think this issue might also be present in the test cases upon submission. If you could let me know what is going on, that would be great. Thanks!
The value of this path is the bitwise OR of all the edge values in the path. Pay attention it's not the sum of the edge values in the path, it's bitwise OR