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 nodes and edges. Edge connects nodes and with a value of . A path from to consists of a sequence of the 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 queries, , can you determine the minimum path *value* of a path from to ?

#### Input Specification

The first line will contain three integers .

The next lines will each contain three integers, , indicating there is an edge between nodes and of value . Note that there may be duplicate edges between nodes. It is guaranteed that the entire graph is connected.

The next lines will each contain two integers, .

#### Output Specification

For each query, output one integer, the minimum path *value*.

#### Subtasks

For 2/15 of the points, .

For an additional 3/15 of the points, .

#### 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

of all the edge values in the path. Pay attention it's not the sum of the edge values in the path, it'sbitwise ORbitwise OR