两个灌溉合作社共享同一个肥沃的山谷。第一个合作社维护着分散在田地里的水泵;第二个负责监管周围山上的水库。每当两个合作社决定铺设一对新管道时,管道必须相交——在这样的交叉点上,他们可以安装一个接头阀。管道始终沿着一对不同的泵或一对不同的水箱之间的直线段。如果两条管道至少共享一个公共点,则它们相交(接触和重叠的管道被视为相交)。
您将获得笛卡尔平面上每个泵和每个水库的精确坐标。对于每个规划方案,确定第一个合作社是否可以选择两个不同的泵,第二个合作社是否可以选择两个不同的水库,以便两条直管相交。如果可能的话,报告这些泵和水库的指数;否则声明该项目无法实现。
输入
第一行包含一个整数 $$$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$$$。
输出
对于每个规划场景:
如果第一个合作社可以选择两台水泵,第二个合作社可以选择两个水库,使得连接每对水泵的直管段相交,则输出四个整数 $$$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$$$。
如果存在多个有效的解决方案,则其中任何一个都是可以接受的。
示例
输入复制
340 04 03 31 35-1 15 12 -12 46 340 01 00 11 145 56 55 66 630 04 00 234 -24 26 1
输出复制
1 4 1 2 -1 1 2 1 2
注意
![]() | ![]() | ![]() |
| 规划场景 1 | 规划场景 2 | 规划场景 3 |



