Problem H
Magical Distances

Photo by TVZ Design

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.

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

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