Marriage

While investigating the machines in the gambling hall, Ralph found what seems to be the most boring game ever made. It bears the proud name "Let's dance." The goal of the game is to match up the best dance pairs from the given boys and girls.

There are $n$ boys in the game, numbered for convenience from $1$ to $n$, and $n$ girls, also numbered from $1$ to $n$. All children are located along the coordinate line, and $i$-th boy is located at the point with coordinate b_i, and the $j$-th girl is located at the point with coordinate g_j. The game is made not very realistic, so it may be that several children are located at the same point.

Of course, children have their own preferences, which, however, are arranged quite simply: let's call the sympathy between the $i$-th boy and $j$-th girl the reciprocal of the distance between them on a straight line, which in turn is calculated by the formula |b_i - g_j|. In other words, the closer the boy and girl are, the more they like each other. Please note that several girls can be equally attractive to one boy at once, and vice versa.

The player must make $n$ pairs, each of which must contain one boy and one girl, and each child must be present exactly once in one of the pairs.

However, not any pairing will do. Let boy $A$ be paired with girl $a$, and boy $B$ be paired with girl $b$. We will say that between the boy $A$ and the girl $b$, there is a temptation if the sympathy between $A$ and $b$ is strictly greater than the sympathy between $A$ and $a$, and also the sympathy between $B$ and $b$. In other words, temptation arises between a boy and a girl if the sympathy between them is greater than the sympathy within their couples.

The goal of the game is to divide all the boys and girls into pairs so that there are no temptations during this division. The game turned out to be surprisingly addictive, but Ralph can't cope with its next level. So he asked you to write a program that either wins this game or determines that it can't be done.