题目描述

两个灌溉合作社共同使用同一片肥沃的山谷。

第一个合作社负责维护散布在田野中的水泵，第二个合作社负责管理周围山丘上的蓄水池。每当两个合作社决定铺设一对新管道时，两条管道必须相交，这样才能在交点处安装一个联合阀门。

每条管道都是连接以下两类点中的两个不同点的直线段：

• 两个不同的水泵；
• 两个不同的蓄水池。

若两条线段至少有一个公共点，则认为两条管道相交。接触和重叠也视为相交。

给定所有水泵和蓄水池在笛卡尔平面上的精确坐标。对于每个规划方案，请判断：

• 第一个合作社能否选择两个不同的水泵；
• 第二个合作社能否选择两个不同的蓄水池；

使连接两对点得到的两条线段相交。

若可以，请输出所选择点的编号；否则输出无解。

输入格式

第一行包含一个整数 $t$，表示规划方案数。

对于每个规划方案：

1. 第一行包含一个整数 $n$，表示水泵数量；
2. 接下来 $n$ 行，每行包含两个整数 $x_i,y_i$，表示第 $i$ 个水泵的坐标；
3. 下一行包含一个整数 $m$，表示蓄水池数量；
4. 接下来 $m$ 行，每行包含两个整数 $u_j,v_j$，表示第 $j$ 个蓄水池的坐标。

同一类中的所有点互不相同，并且没有水泵与蓄水池位于同一个位置。

输出格式

对于每个规划方案：

• 若存在满足条件的选择，输出四个整数 $p_1,p_2,r_1,r_2$：
  • $p_1,p_2$ 是两个不同水泵的编号；
  • $r_1,r_2$ 是两个不同蓄水池的编号；
  • 线段 $p_1p_2$ 与线段 $r_1r_2$ 必须相交。
• 若不存在满足条件的选择，输出 -1。

若有多组合法答案，输出任意一组即可。

样例

3
4
0 0
4 0
3 3
1 3
5
-1 1
5 1
2 -1
2 4
6 3
4
0 0
1 0
0 1
1 1
4
5 5
6 5
5 6
6 6
3
0 0
4 0
0 2
3
4 -2
4 2
6 1

1 4 1 2
-1
1 2 1 2

样例说明

下图展示了三个规划方案。圆点表示水泵，方点表示蓄水池，粗线表示样例输出中选择的管道。

数据范围

所有规划方案中的 $n$ 之和不超过 $2\cdot 10^5$，$m$ 之和也不超过 $2\cdot 10^5$。