CF2181I.Irrigation Interlock

Two irrigation cooperatives share the same fertile valley. The first cooperative maintains pumps scattered across the fields; the second supervises reservoirs on the surrounding hills. Whenever both cooperatives decide to lay a pair of new pipes, the pipes must intersect — at such an intersection they can install a joint valve. Pipes always follow a straight line segment between a pair of distinct pumps or a pair of distinct reservoirs. Two pipes intersect if they share at least one common point (touching and overlapping pipes are considered intersecting).

You are given the exact coordinates of every pump and every reservoir on a Cartesian plane. For each planning scenario, determine whether the first cooperative can pick two distinct pumps and the second cooperative can pick two distinct reservoirs so that the two straight pipes intersect. If this is possible, report the indices of those pumps and reservoirs; otherwise declare that the project cannot be realized.

两个灌溉合作社共享同一片肥沃的山谷。第一个合作社负责维护散布在田地中的水泵；第二个合作社负责监管周围山丘上的水库。每当两个合作社决定铺设一对新管道时，这两条管道必须相交——在该交点处，他们可以安装一个联合阀门。管道始终沿连接一对不同水泵或一对不同水库的直线段铺设。若两条管道至少有一个公共点（即相切或重叠的管道也被视为相交），则称它们相交。

你将获得笛卡尔平面上所有水泵与所有水库的精确坐标。对于每种规划情形，请判断：第一个合作社能否选出两个不同的水泵，同时第二个合作社能否选出两个不同的水库，使得所铺设的两条直线管道相交。若可行，请报告所选水泵与水库的索引；否则，声明该项目无法实施。

The first line contains an integer $t$ ($1 \le t \le 10^5$) — the number of planning scenarios.

For each planning scenario:

The first line contains an integer $n$ ($2 \le n \le 10^5$) — the number of pumps managed by the first cooperative.

Each of the next $n$ lines contains two integers $x_i$ and $y_i$ ($|x_i|, |y_i| \le 10^9$) — the Cartesian coordinates of pump $i$. The pump locations are distinct.

The next line contains an integer $m$ ($2 \le m \le 10^5$) — the number of reservoirs managed by the second cooperative.

Each of the next $m$ lines contains two integers $u_j$ and $v_j$ ($|u_j|, |v_j| \le 10^9$) — the Cartesian coordinates of reservoir $j$. The reservoir locations are distinct.

No pump shares its location with any reservoir.

It is guaranteed that the sum of $n$ over all planning scenarios does not exceed $2 \cdot 10^5$ and the sum of $m$ over all planning scenarios does not exceed $2 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \le t \le 10^5$）—— 规划场景的数量。

对于每个规划场景：

第一行包含一个整数 $n$（$2 \le n \le 10^5$）—— 第一合作社所管理的泵的数量。

接下来的 $n$ 行中，每行包含两个整数 $x_i$ 和 $y_i$（$|x_i|, |y_i| \le 10^9$）—— 泵 $i$ 的笛卡尔坐标。所有泵的位置互不相同。

接下来一行包含一个整数 $m$（$2 \le m \le 10^5$）—— 第二合作社所管理的水库的数量。

接下来的 $m$ 行中，每行包含两个整数 $u_j$ 和 $v_j$（$|u_j|, |v_j| \le 10^9$）—— 水库 $j$ 的笛卡尔坐标。所有水库的位置互不相同。

任意泵的位置均不与任一水库重合。

保证所有规划场景中 $n$ 的总和不超过 $2 \cdot 10^5$，且所有规划场景中 $m$ 的总和不超过 $2 \cdot 10^5$。

For each planning scenario:

If the first cooperative can choose two pumps and the second cooperative can choose two reservoirs so that the straight pipes connecting each pair intersect, output four integers $p_1$, $p_2$, $r_1$, $r_2$ — the indices of two chosen pumps ($1 \le p_1, p_2 \le n$; $p_1 \ne p_2$) and two chosen reservoirs ($1 \le r_1, r_2 \le m$; $r_1 \ne r_2$).

If such an intersection is impossible, output $-1$.

In case several valid solutions exist, any one of them is acceptable.

对于每种规划场景：

若第一个合作社可以选择两台水泵，第二个合作社可以选择两个水库，使得连接每对设施的直线管道相交，则输出四个整数 $p_1$、$p_2$、$r_1$、$r_2$ —— 即所选两台水泵的编号（$1 \le p_1, p_2 \le n$；$p_1 \ne p_2$）和所选两个水库的编号（$1 \le r_1, r_2 \le m$；$r_1 \ne r_2$）。

若无法实现上述相交，输出 $-1$。

若存在多种可行解，输出任意一种即可。

Planning scenario 1

Planning scenario 2

Planning scenario 3

规划场景 1

规划场景 2

规划场景 3