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