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.