P12806 [AMPPZ 2019] The Great Drone Show

Source: [AMPPZ 2019](https://amppz.tcs.uj.edu.pl/2019/data.html).

今年的盛大无人机表演将会取得惊人成功！当然，前提是没有任何事情出大错。并且每个人都按计划行事。 计划已经详细制定。开始时，有 $n$ 架无人机停在地面上。为了描述它们的运动，我们引入标准的三维欧几里得坐标系，其中地面是 $z = 0$ 平面。第 $i$ 架无人机的起始位置被描述为 $(x_i, y_i, 0)$。 为了在表演期间允许通信，有 $m$ 条电缆连接在无人机对之间。电缆最初也放置在地面上，以直线段的形式连接一些无人机对。已知从每架无人机到其他每架无人机都有一条电缆序列（电缆网络是连通的）。此外，为了避免电缆缠结，**没有两条线段相交**（它们只能有公共端点）。 在表演期间，将执行一系列 $k$ 个动作。每个动作包括改变一架无人机的高度（即 $z$ 坐标）。每个动作将平滑执行，并且只有在前一个动作结束后才开始。在一个动作期间，一些无人机之间的距离可能改变——幸运的是，电缆可以一定程度地拉伸。对于每条电缆，我们知道它能承受的最大长度——如果其端点无人机之间的距离超过这个值，电缆就会断裂。 表演组织者预见到一些电缆可能会断裂。然而，一些无人机对必须保持能够直接或间接通信。给定 $q$ 个特定的**关键**无人机对，确定在表演期间的某个时刻这些对之间的通信是否变得不可能，如果是，确定导致连接丢失的动作。

**本题单个测试点内有多组测试数据。** 输入的第一行包含测试数据的组数 $z$（$1 \le z \le 400$）。 每组测试数据格式如下： 第一行包含无人机的数量 $n$（$2 \le n \le 500\ 000$）。 接下来的 $n$ 行每行包含两个整数 $x_i, y_i$（$|x_i|, |y_i| \le 10^8$）——第 $i$ 架无人机的 $x$ 和 $y$ 坐标。 没有两架无人机占据相同的起始位置。 下一行包含一个整数 $m$（$1 \le m \le 3 \cdot n$）——电缆的数量。 接下来的 $m$ 行每行描述一条电缆，包含三个整数 $u, v, l$（$1 \le u \ne v \le n$；$1 \le l \le 10^9$）——分别是连接的无人机编号和其最大长度。 一对无人机最多只能由一条电缆连接。 每条电缆在其起始位置的长度都在给定的长度限制内。 下一行包含动作的数量 $k$（$1 \le k \le 500\ 000$）。 接下来的 $k$ 行每行包含两个整数 $v, h$（$1 \le v \le n$；$|h| \le 10^9$）——移动无人机的编号和其高度的变化（正数表示无人机上升，负数表示下降）。 你可以假设没有无人机下降到地面以下（$z$ 坐标保持非负）。 最后，下一行包含一个整数 $q$（$1 \le q \le 500\ 000$）——需要检查的关键对的数量。 在接下来的 $q$ 行中，这些对被描述——每行包含两个无人机编号 $u, v$（$1 \le u \ne v \le n$）。 所有测试数据中 $n$ 值的总和不超过 $1\ 000\ 000$。 类似地，$k$ 值的总和和 $q$ 值的总和也都不超过 $1\ 000\ 000$。

对于每个测试数据，输出 $q$ 个整数，每个占一行——每个关键对的答案。对于每个这样的无人机对，输出导致它们失去通信能力的第一个动作的编号。 动作从 1 开始编号。如果一个关键对在整个表演期间保持连通，则输出 $\texttt{-1}$。