今年的无人机表演将会是一场惊艳的盛会！前提是不要出什么大乱子，并且每个人都严格按照计划行事。

计划的每一个细节都已制定完毕。起初，$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 \neq 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 \neq v \le n$)。

所有测试用例中 $n$ 的总和不超过 $1\,000\,000$。同样，所有测试用例中 $k$ 的总和与 $q$ 的总和也均不超过 $1\,000\,000$。

输出格式

对于每个测试用例，在单独的行中输出 $q$ 个整数，作为每个关键无人机对的答案。对于每一对无人机，输出导致它们失去通信能力的第一次移动的编号。移动编号从 1 开始。如果一对关键无人机在整个表演过程中始终保持连通，则输出 $-1$。

样例

输入 1

1
4
0 0
0 12
0 24
0 25
3
1 2 13
2 3 13
3 4 1
4
3 1
2 6
3 1
2 -6
4
1 2
2 3
3 4
1 4

输出 1

2
-1
1
1