The Great Drone Show

This year's Great Drone Show is planned to be a big success, provided nothing goes wrong and everyone follows the plan.

The plan is worked out in every detail. At the beginning, $n$ drones are parked on the ground. To describe their movement, we use standard Euclidean coordinates in three dimensions, where the ground is the plane $z = 0$. The starting position of the $i$-th drone is $(x_i, y_i, 0)$.

To allow communication during the show, there are $m$ cables between pairs of drones. Initially the cables also lie on the ground, as straight segments connecting some pairs of drones. The cable network is connected: from every drone there is a sequence of cables to every other drone. To avoid tangling, no two segments cross (they can only share endpoints).

During the show, a sequence of $k$ moves is performed. Each move changes the height (the $z$ coordinate) of one drone. Each move is performed smoothly, and it starts only after the previous one ends. During a move, the distances between some drones may change, and the cables can stretch to some degree. Each cable has a maximal length. If its endpoint drones move farther apart than this value, the cable breaks.

The organizers expect some cables to break. However, some pairs of drones must stay able to communicate, directly or indirectly. Given $q$ critical pairs of drones, determine whether communication between a pair becomes impossible at some point during the show. If it does, determine the move that causes the connection loss.

The first line contains the number of test cases $z$ ($1 \le z \le 400$). Each test case has the following format.

The first line contains $n$ ($2 \le n \le 500000$). Each of the next $n$ lines contains two integers $x_i$, $y_i$ ($|x_i|, |y_i| \le 10^8$), the coordinates of the $i$-th drone. No two drones share a starting location.

The next line contains $m$ ($1 \le m \le 3n$), the number of cables. Each of the next $m$ lines contains three integers $u$, $v$, $l$ ($1 \le u, v \le n$, $u \ne v$; $1 \le l \le 10^9$): the two connected drones and the maximal length of the cable. A pair of drones is connected by at most one cable. The length of each cable at its starting position is within its limit.

The next line contains $k$ ($1 \le k \le 500000$). Each of the next $k$ lines contains two integers $v$, $h$ ($1 \le v \le n$, $|h| \le 10^9$): the moving drone and its change in height. A positive $h$ raises the drone, and a negative $h$ lowers it. You may assume that no drone ever goes below the ground, so all $z$ coordinates stay non-negative.

Finally, the next line contains $q$ ($1 \le q \le 500000$), the number of critical pairs. Each of the next $q$ lines contains two drone numbers $u$, $v$ ($1 \le u, v \le n$, $u \ne v$).

Over all test cases, the sum of $n$ values does not exceed $1000000$, and the sums of $k$ and of $q$ each do not exceed $1000000$.

For every test case, print $q$ integers on separate lines, one per critical pair, in input order. For each pair, print the number of the first move after which the two drones can no longer communicate. Moves are numbered from 1. If a pair stays connected through the whole show, print $-1$.