See-saw

[morris821028]

Problem Description

Given a set of odd positive integers and build a balanced see-saw. Imagine that we have a stick of length $n$, where $n$ is an odd number, and a set of $n$ positive integers. Now we support the stick in the middle and place the $n$ numbers along the stick evenly, and we have a see-saw. Now please place the numbers so that the see-saw is balanced.

Let us consider an example. Let $n$ be 5 and the numbers are 1, 2, 3, 1, and 5. If we place the numbers as 3, 1, 5, 3, 2 then the seesaw is balanced because $3 \times 2 + 1 \times 1 = 3 \times 1 + 2 \times 2$.

Another vaild solution is 2, 1, 3, 1 because $2w \times 2 + 1w \times 1 = 3w \times 1 + 1w \times 2$

Subtasks

• 5pt. $n = 3$
• 10pt. $n = 5$
• 30pt. $n$ is no more than 9
• 55pt. $n$ is no more than 17

  Input Format

There are many cases in one input file. Please read the input file until the EOF.

For each case, there are two lines in each case. The first line contains a number $n$ which means the number of the set of the positive integers. And then there are n numbers in the second line which means the set of the positive integers.

Output Format

If the see-saw can be balanced, print one possible solution.

If the see-saw can not be balanced, print N.

Sample Input 1

3
1 1 6
3
9 4 5
3
9 5 9

Sample Output 1

1 _^_ 1
N
9 _^_ 9

Sample Input 2

5
1 2 3 1 5
9
3 9 1 3 7 5 5 2 8
11
8 2 7 1 1 9 9 1 3 9 4

Sample Output 2

2 1 _^_ 3 1
8 3 1 3 _^_ 9 7 5 2
3 9 1 1 8 _^_ 2 7 9 4 1