Balanced Partition of a List

You are given a list of integers. Your task is to partition this list into two nonempty sublists such that the absolute difference between the sum of the numbers in the two sublists is minimized. Formally, let \(S\) and \(T\) be a partition of the original list (with \(S \cup T\) equal to the list and \(S \cap T = \emptyset\)), and let \(sum(S)\) and \(sum(T)\) denote the sums of the numbers in each sublist. You need to choose a partition that minimizes \(|sum(S)-sum(T)|\). If there are multiple partitions achieving the same minimum difference, output the one corresponding to the smallest bitmask when iterating over all nonempty proper subsets in increasing order. The numbers in each output sublist should be in the same order as in the input.

Note: The input size is small enough (e.g. \(n \leq 20\)) so that an exhaustive search over all possible partitions is acceptable.

inputFormat

The first line contains a single integer \(n\) indicating the number of elements in the list. The second line contains \(n\) integers separated by spaces.

outputFormat

Output two lines. The first line should contain the elements of the selected sublist (corresponding to the chosen bitmask) separated by spaces, and the second line should contain the remaining elements (in their original order) separated by spaces.

If there are multiple valid answers, any one of them is acceptable but your program must follow the deterministic procedure described in the statement.

## sample

5
3 1 4 2 2

3 1 2
4 2

</p>