Одруження

Досліджуючи автомати в ігровій залі, Ральф натрапив на, мабуть, найскучнішу гру з усіх, що коли-небудь існували. Вона має горду назву «Давай потанцюємо». Завдання гри полягає в тому, щоб скласти вдалі пари для танцю з наданих гравцю хлопчиків і дівчаток.

У грі є $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$. Іншими словами, спокуса виникає, якщо симпатія між хлопчиком і дівчинкою більша, ніж симпатія всередині їхніх пар.

Мета гри — розбити всіх хлопчиків і дівчаток на пари так, щоб не виникало спокус. Гра виявилася на диво захоплюючою, але Ральф ніяк не може впоратися з черговим її рівнем. Тому він попросив вас написати програму, яка виграватиме в цю гру або визначить, що це неможливо.