Secret Agent

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.

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.

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.

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