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