Женитьба
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Исследуя автоматы в игровом зале, Ральф, нашел, кажется, самую скучную из когда-либо созданных игр. Она носит гордое название «Давай потанцуем». Цель игры заключается в том, чтобы составить удачные пары для танца из данных игроку мальчиков и девочек.

В игре есть $$$n$$$ мальчиков, пронумерованных для удобства от $$$1$$$ до $$$n$$$, и $$$n$$$ девочек, также пронумерованных от $$$1$$$ до $$$n$$$. Все дети расположены вдоль координатной прямой, причем $$$i$$$-й мальчик расположен в точке с координатой $$$b_i$$$, а $$$j$$$-я девочка расположена в точке с координатой $$$g_j$$$. Игра сделана не очень реалистично, поэтому может быть такое, что несколько детей располагаются в одной точке.

Разумеется, у детей есть свои предпочтения, которые, правда, устроены довольно просто: назовем симпатией между $$$i$$$-м мальчиком и $$$j$$$-й девочкой величину, обратную расстоянию между ними на прямой, которое в свою очередь вычисляется по формуле $$$|b_i - g_j|$$$. Иными словами, чем ближе располагаются мальчик и девочка, тем больше они нравятся друг другу. Обратите внимание, что одному мальчику могут быть одинаково симпатичны сразу несколько девочек, и наоборот.

Игрок должен составить $$$n$$$ пар, в каждой из которых должен быть один мальчик и одна девочка, при этом каждый ребенок должен ровно один раз присутствовать в одной из пар.

Однако не любое разбиение на пары подойдет. Пусть мальчик $$$A$$$ находится в паре с девочкой $$$a$$$, а мальчик $$$B$$$ находится в паре с девочкой $$$b$$$. Будем говорить, что между мальчиком $$$A$$$ и девочкой $$$b$$$, возникает соблазн, если симпатия между $$$A$$$ и $$$b$$$ строго больше, чем симпатия между $$$A$$$ и $$$a$$$, а также симпатия между $$$B$$$ и $$$b$$$. Иными словами, между мальчиком и девочкой возникает соблазн, если симпатия между ними больше, чем симпатия внутри их пар.

Цель игры — разбить всех мальчиков и девочек на пары так, чтобы при этом разбиении не возникало соблазнов. Игра оказалась на удивление затягивающей, однако Ральф никак не может справиться с очередным ее уровнем. Поэтому он попросил вас написать программу, которая будет выигрывать в эту игру либо определять, что это сделать невозможно.

Входные данные

Первая строка входных данных содержит единственное целое число $$$n$$$ — количество мальчиков и девочек ($$$1 \le n \le 10^5$$$).

Вторая строка содержит $$$n$$$ целых чисел $$$b_i$$$ — координаты мальчиков на прямой ($$$1 \le b_i \le 10^9$$$).

Третья строка содержит $$$n$$$ целых чисел $$$g_i$$$ — координаты девочек на прямой ($$$1 \le g_i \le 10^9$$$).

Выходные данные

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

В противном случае выведите $$$n$$$ строк, указывающих подходящее разбиение на пары. Каждая строка должна содержать два целых числа от $$$1$$$ до $$$n$$$ — номер мальчика и девочки в очередной паре соответственно.

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

Пример

Входные данные
3
6 12 18
3 9 16
Выходные данные
3 3
1 2
2 1