题目描述

Flatland 联邦大学的体育编程成就博物馆中，有一个凸多边形大厅，纪念品是大厅内部的一些点。

为了保护纪念品，馆长希望用一个或两个三角形区域把纪念品围起来。每个三角形的三个顶点必须是大厅凸多边形的顶点。选择的两个三角形（如果选两个）不能有公共内部，即它们交集面积为 0。每个纪念品必须位于至少一个选中三角形内部。

馆长希望对游客造成的不便最少，因此要最小化选中三角形面积之和。每个三角形面积必须严格为正。

请输出一个面积和最小的方案。

输入格式

输入包含一个或多个测试点。

第一行包含整数 $t$，表示测试点数量。

每个测试点格式如下：

第一行包含两个整数 $n,m$，表示大厅凸多边形顶点数和纪念品数量。

接下来 $n$ 行，每行两个整数 $x^h_i,y^h_i$，表示大厅顶点坐标。顶点按逆时针顺序给出。

接下来 $m$ 行，每行两个整数 $x^s_i,y^s_i$，表示纪念品坐标。

约束：

• $3\le n\le 2000$；
• $1\le m\le 2000$；
• 坐标绝对值不超过 $10^9$；
• 所有纪念品严格位于大厅内部；
• 给出的 $n+m$ 个点中任意三点不共线；
• 单个输入文件中所有测试点的 $n$ 之和不超过 2000，所有 $m$ 之和不超过 2000。

输出格式

对每个测试点：

若无法选择一个或两个三角形满足要求，输出：

-1

否则第一行输出整数 $k$，表示选择的三角形个数，$1\le k\le 2$。接下来 $k$ 行，每行三个整数，表示一个三角形的三个大厅顶点编号。

若有多种最优答案，输出任意一种。

注意：只需要最小化三角形面积和。

样例输入

3
4 1
0 0
5 0
4 4
0 4
2 3
5 3
0 0
6 -6
11 0
8 4
3 4
3 2
7 3
8 -2
8 4
-4 -4
0 -7
4 -4
6 0
4 4
0 7
-4 4
-6 0
-2 -5
2 -5
3 2
-3 2

样例输出

1
1 4 3
-1
2
1 3 2
4 8 6

图片说明

给出了三个测试点的示意图：第一个和第三个展示了最优选取的三角形，第二个展示了无法用一或两个满足条件的三角形覆盖全部纪念品的情况。