# Problem H

Magical Distances

There are $n$ cities in the Magical Island, numbered from $1$ to $n$. These cities are connected by $m$ bi-directional roads such that there exists a path between every pair of cities. There may be multiple roads between two cities. Each road has a positive length.

Magical crystals are the most important resources transported between the cities in the Magical Island. The cost of sending one magical crystal from city $s$ to city $t$ equals the smallest distance of any path between city $s$ and city $t$. The distance of a path in the Magical Island is a bit special though: It is the bitwise OR value of all the road lengths on this path.

In each of the next $q$ days, exactly one magical crystal will be transported between a pair of cities. Help the Magical Island figure out the transportation cost for each day.

## Input

The first line contains two integers $n, m$ ($2\leq n\leq 10^5,1\leq m\leq n+200$). Each of the next $m$ lines contains three integers $a, b, w$ that describe a road connecting city $a$ and city $b$ with length $w$ ($1\leq a, b\leq n, a \neq b, 1\leq w \leq 10^9$). In the next line, there is a single integer $q$ $(1\leq q\leq 10\, 000)$, the number of days to consider. The next $q$ lines each have two integers $s$ and $t$ ($1\leq s, t\leq n, s \neq t$). The $i$th line indicates that on day $i$ a crystal is sent from city $s$ to city $t$.

## Output

For each of the $q$ days, output the cost of sending the crystal from $s$ to $t$ for that day.

Sample Input 1 | Sample Output 1 |
---|---|

4 7 1 2 1 1 2 3 1 3 2 1 4 1 2 3 4 2 4 4 3 4 4 3 1 2 1 3 3 4 |
1 2 3 |

Sample Input 2 | Sample Output 2 |
---|---|

6 6 1 2 1 2 3 2 3 4 3 4 5 4 5 6 5 6 1 6 3 1 4 2 5 3 6 |
3 7 7 |