A KitKat is a candy bar that can be split into two equal sized pieces. One day while Christmas shopping, Roger stumbles upon the legendary $N$-kat: a KitKat that can be split into $N$ equally sized pieces, with the $i^{\text{th}}$ piece having sweetness $s_i$. Roger wishes to split the pieces into two disjoint non-empty subsets to share with his two friends such that the total sweetness of the two subsets has the smallest possible non-negative difference. Note that the two subsets do not need to contain all $N$ elements; Roger will eat any pieces his friends do not get. Help Roger split the $N$-kat!

Note that the judge will accept any valid solution.

Hint: It is recommended Python users use PyPy instead.

Constraints

$1\le s_i\le {10}^6$

Subtask 1 [20%]

$2\le N\le 10$

Subtask 2 [80%]

$2\le N\le 20$

Input Specification

The first line of input will contain a single integer, $N$.
The next line of input will contain $N$ space-separated integers, $s_1,s_2,\dots ,s_N$.

Output Specification

The output should consist of two lines.
The first line should contain $a_1{a}_2\dots$, indicating that the first subset should contain piece $a_1,a_2,\dots$.
The second line should contain $b_1{b}_2\dots$, indicating that the second subset should contain piece $b_1,b_2,\dots$.

Sample Input

4
8 2 3 1

Sample Output

2 4
3

Explanation for Sample Output

The first subset contains pieces $2$ and $4$, which have a total sweetness of $3$.
The second subset contains piece $3$, which has a sweetness of $3$.
The difference between the total sweetness of both subsets is $0$, which is the smallest difference possible.