Secret Agent

Time limit2sMemory limit512 MB

Summary

Given a planar straight-line graph (castle walls) where crossing a wall costs its height, find the minimum cost to travel between successive query points, starting from infinity.

Level: Hard9 of 10
Topics: Graph, Geometry, Shortest path, DFS
Solved: No attempts yet

Problem

Two thousand years ago the castle of the city state Inho stood on this very spot. The castle has $N$ watchtowers numbered $1$ through $N$ and $M$ walls, each wall joining two towers. Every wall is a straight segment, no two walls meet at any point other than a tower, and the walls let you walk from any tower to every other tower. King Inho of Inho hid the state secrets inside that castle.

King Minseok of the rival city state Minseok sends a secret agent in to dig the secrets out. The agent is so fast that travel time is negligible whenever no wall blocks the way. Climbing over a wall costs exactly the height of that wall. The agent cannot pass through a tower, so every crossing happens at a point of a wall that is not a tower.

Minseok orders the agent to visit $Q$ spots in the given order. No spot lies on a wall or on a tower. The agent starts infinitely far away from the castle, goes to spot $1$ , then to spot $2$ , and so on. Find the minimum time each leg of the trip takes.

Input

The first line contains the number of towers $N$ ( $1 \le N \le 200\,000$ ) and the number of walls $M$ ( $N-1 \le M \le N+100$ ).

Each of the next $N$ lines contains the coordinates $x_i$ and $y_i$ of tower $i$ . ( $|x_i|, |y_i| \le 10^9$ )

Each of the next $M$ lines contains the numbers $u_i$ and $v_i$ of the two towers a wall joins, followed by the height $h_i$ of that wall. ( $1 \le u_i, v_i \le N$ , $u_i \ne v_i$ , $1 \le h_i \le 10^9$ )

At most one wall joins a given pair of towers, and no two walls meet at a point other than a tower. Every tower is reachable from every other tower along the walls.

The next line contains the number of orders $Q$ ( $1 \le Q \le 200\,000$ ).

Each of the next $Q$ lines contains the coordinates $a_i$ and $b_i$ of the $i$ -th spot. ( $|a_i|, |b_i| \le 10^9$ )

No spot lies on a wall or on a tower.

Output

Print $Q$ lines. Line $i$ holds the minimum time needed to travel from spot $i-1$ to spot $i$ . Spot $0$ sits at $(\infty, \infty)$ , infinitely far from the castle.

Hint

The picture below shows a castle with 4 towers and 5 walls, together with the 3 spots visited in order.

Examples3

Example 1

Input

Expected output

4
2
3

Example 2

Input

8 9
0 0
20 0
20 20
0 20
5 5
15 5
15 15
5 15
1 2 10
2 3 12
3 4 11
4 1 13
5 6 1
6 7 2
7 8 3
8 5 4
1 5 1000000000
5
10 10
18 10
25 10
0 25
10 3

Expected output

Example 3

Input

Expected output