Gifts Delivery

Limits: 2 sec., 256 MiB

On Christmas Eve Santa Claus must deliver several gifts between some pairs of houses in Brzhentykewyczhi.

The city of Brzhentykewyczhi has N houses and M bidirectional roads between houses. It is possible to travel between every pair of houses using these roads. Each road has some capacity C - the largest number of gifts that can be transported using this road. It so happens that capacity values of roads in this city are all distinct.

Santa Claus wants to make Q trips between pairs of houses a,b. For each trip Santa uses the following process:

1. Among all routes between houses a,b, Santa chooses the one through which he can carry the largest number of gifts (lets call this number S). Santa Claus can carry a certain number of gifts using some route, if he can carry it through every road of that route.

2. Santa Claus deletes the road with capacity S – it is guaranteed that it exists and is unique since all capacities are distinct. This road has the smallest capacity in the chosen route.

3. Santa adds a road between houses a, b with capacity S.

It is guaranteed that after each request there still exists a path between every pair of houses. Santa asked you to compute the value of S for every request.

Input

Two positive integers N, M - number of houses and roads.

Next M rows have three integers each u, v, p - there exists a road between houses u, v with capacity p.

Next line has a positive integer Q - number of requests.

Next Q lines have two integers each a, b - the route that Santa needs to take.

Output

For each request output the value of S for that request, separated by newlines.

Constraints

\(1 \leq N \leq 10^5\),

\(1 \leq M \leq 2 \cdot 10^5\),

\(1 \leq u,v \leq N\), \(u \neq v\),

\(1 \leq C_i \leq 10^9\),

\(1 \leq Q \leq 10^5\),

\(1 \leq a,b \leq N\), \(a \neq b\).

Samples

Input (stdin) сopy	Output (stdout) сopy
4 4 1 2 2 2 3 3 3 1 4 1 4 1 2 1 2 3 4	3 1

Notes

After first request Santa deletes the road between houses \(2\) and \(3\) with capacity \(3\) and adds a road with capacity \(3\) between houses \(1\) and \(2\).