Задача G. Мосты-горки ≡

Условие

Выбор подходящего проекта строительства моста на остров Русский — задача не из лёгких: ведь существует много разновидностей мостов.

В Академии был разработан новый тип мостов — мосты-горки. Эти мосты устанавливаются между двумя островами, один из которых должен быть высоким, а другой низким. Чтобы попасть с высокого острова на низкий, достаточно просто скатиться по мосту, как по горке. При этом даже не нужно тратить топливо! К тому же при достаточной массе автомобиля езда превращается в увлекательный аттракцион.

Но у мостов-горок есть и недостатки:

1. Мост должен быть идеально прямым: массивные автомобили могут не справиться с поворотами на большой скорости.
2. Конструкция мостов-горок такова, что один мост не может проходить над другим мостом, то есть мосты не должны пересекаться друг с другом.

Ввиду заинтересованности правительства в мостах-горках в Академии была организована лаборатория по их исследованию. В лабораторных условиях была создана модель архипелага, в котором N высоких и N низких островов представлены точками на плоскости, причём никакие три острова не лежат на одной прямой. Требуется построить ровно N мостов-горок между островами так, чтобы на каждом острове был мост. Как высокие, так и низкие острова пронумерованы от 1 до N.

Первый пример теста соответствует рисунку справа. Тёмными изображены острова с номером 1, а светлыми — с номером 2. Если соединить тёмные острова со светлыми, то мосты будут пересекаться.

Формат входного файла

Входной содержит число N, за которым следует N пар чисел X_i Y_i — координаты высоких островов, а затем N пар чисел x_i y_i — координаты низких островов.

Формат выходного файла

Выходной файл должен содержать N пар чисел p_i q_i — номера островов, соединённых мостом, где p_i — номер высокого острова, q_i — номер низкого острова. Пары можно выводить в произвольном порядке. Если решений несколько, выведите любое из них.

Если N мостов-горок построить невозможно, то выходной файл должен содержать единственное число −1.

Ограничения

1 ≤ N ≤ 1000, −10⁵ ≤ X_i, Y_i, x_i, y_i ≤ 10⁵.

Все числа во входном файле целые.

Примеры тестов

2
0 0
1 0
-2 -3
2 -3

1 1
2 2

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

1 3
4 1
2 2
5 4
3 5