Country A has $n$ cities, numbered from $1$ to $n$. There are $m$ bidirectional roads between the cities. Each road has a weight limit, referred to as the load limit. Now there are $q$ trucks transporting goods. The drivers want to know the maximum weight of goods they can carry without exceeding the load limit of any road on their route.

Input

The first line contains two space-separated integers $n$ and $m$, representing the number of cities and the number of roads in Country A.

The next $m$ lines each contain three space-separated integers $x, y, z$, representing a road between city $x$ and city $y$ with a load limit of $z$. Note: $x \neq y$, and there may be multiple roads between two cities.

The next line contains a single integer $q$, representing the number of trucks that need to transport goods.

The next $q$ lines each contain two space-separated integers $x, y$, representing a truck that needs to transport goods from city $x$ to city $y$. Note: $x \neq y$.

Output

Output $q$ lines, each containing one integer, representing the maximum load for each truck. If the destination cannot be reached, output $-1$.

Examples

Input 1

4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3

Output 1

3
-1
3

Constraints

For $30\%$ of the data, $0 < n < 1,000$, $0 < m < 10,000$, $0 < q < 1,000$; For $60\%$ of the data, $0 < n < 1,000$, $0 < m < 50,000$, $0 < q < 1,000$; For $100\%$ of the data, $0 < n < 10,000$, $0 < m < 50,000$, $0 < q < 30,000$, $0 \le z \le 100,000$.