19866번 - Музей 스페셜 저지다국어

В Федеральном Университете Флатландии открылся музей спортивных достижений. Главная гордость этого музея --- зал, в котором расположены сувениры со всевозможных соревнований по спортивному программированию.

Программирование становится всё популярнее, и заинтересованных посетителей этого зала становится всё больше, поэтому директор музея начинает беспокоиться о сохранности своих сувениров. Для начала директор решил оградить одну или две зоны с сувенирами от посетителей так, чтобы они не могли свободно бродить между ними, а могли лишь смотреть со стороны.

Зал имеет форму выпуклого многоугольника, а сувениры --- это точки внутри этого многоугольника. Директор хочет выбрать один или два треугольника с вершинами в углах зала, так чтобы эти треугольники не имели общей внутренней части (то есть площадь их пересечения была равна нулю), а каждый сувенир оказался внутри одного из треугольников.

Директор хочет доставить посетителям как можно меньше неудобств, поэтому суммарная площадь выбранных треугольников должна быть минимальной, при этом площадь каждого треугольника должна быть строго положительной. 

Помогите директору оградить экспонаты.

Входные данные содержат один или несколько тестовых примеров.

В первой строке находится число $t$ --- количество тестовых примеров. Далее следуют $t$ блоков, каждый из которых выглядит следующим образом.

В первой строке блока находится два целых положительных числа $n$ и $m$ --- количество вершин в многоугольнике, форму которого имеет зал, и количество сувениров в зале ($3 \le n \le 2000$, $1 \le m \le 2000$).

В следующих $n$ строках находятся по два целых числа $xh_i$ и $yh_i$ --- координаты вершин многоугольника в декартовой системе координат ($-10^9 \le xh_i, yh_i \le 10^9$). Вершины даны в порядке обхода против часовой стрелки.

В следущих $m$ строках находятся по два целых числа $xs_i$, $ys_i$ --- координаты сувениров ($-10^9 \le xs_i, ys_i \le 10^9$) .

Гарантируется, что все сувениры находятся строго внутри зала, а также что никакие три из данных $n + m$ точек не лежат на одной прямой.

Сумма всех $n$ и сумма всех $m$ во всех тестовых примерах одних входных данных не превосходят $2000$ каждая.

Для каждого из $t$ тестовых примеров выведите следующее.

Если невозможно выбрать один или два треугольника требуемым образом, выведите в отдельной строке $-1$.

Иначе выведите в первой строке целое число $k$ ($1 \le k \le 2$) --- количество выбранных треугольников, и в каждой из следующих $k$ строк выведите по три целых числа --- номера вершин зала, которые являются вершинами треугольника.

Если оптимальных ответов несколько, выведите любой из них.

Обратите внимание, что требуется минимизировать только суммарную площадь выбранных треугольников.

На рисунке показаны оптимальные способы выбрать треугольники в первом и третьем тестовых примерах, а также расположение сувениров во втором тестовом примере, где выбрать один или два треугольника нельзя.