| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 19 | 5 | 4 | 22.222% |
Исследуя автоматы в игровом зале, Ральф, нашел, кажется, самую скучную из когда-либо созданных игр. Она носит гордое название <<Давай потанцуем>>. Цель игры заключается в том, чтобы составить удачные пары для танца из данных игроку мальчиков и девочек.
В игре есть $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