Divide and stay Happy. Who cares about the Conquer part? Well, when I buy gifts for my two wives, I want them to feel equally important to me, but it's hard to go shopping with fixed budgets. Instead, I buy a bunch of stuff and divide them into two groups with as equal value as possible. Then I buy a bunch of chocolates to fix the rest.

But I don't want do all the hard lifting when my computer can do it. And you don't either. So solve this problem so that the next time you need to divide gifts among your wives, you know it would be easy.

Input

1 array of (N*2) elements where N*2 is specified in the 1st line.
The elements of the array in the following line.

Output

2 array of N elements each such that:
Difference of (Sum of elements of array 1) and (Sum of elements of array 2) is as close as possible to 0.

Example

Input

4
1 2 3 4 


Output

1 4
2 3
diff=0


Disclaimer: I don't have two wives. But when I feel bad, I imagine having two wives. And suddenly, I am thankful and happy that I have only one. :D
Java

Trying to solve this problem in two phases:

Build two equally sized lists by adding the remaining biggest to the currently smaller list and the next to the other. Repeat.
Identify items from both lists that can be switched to reduce the difference in value

Input like

8
1 2 3 4 5 6 7 8


is already solved after phase 1 as e.g.

2 3 5 8
1 4 6 7
diff=0


and input like

6
1 4 5 6 7 8


will need both phases so that

1 5 8
4 6 7
diff=3


(after phase one) becomes the result of

1 6 8
4 5 7
diff=1


While I can guarantee this attempt will always provide a solution, I can not prove that a optimal solution is found in all cases. With the restriction of equally sized lists it however feels quite realistic that there are no corner cases left behind. Prove me wrong ;-)
Program on ideone.com
import java.util.*;

/**
 * Created to solve http://codegolf.stackexchange.com/q/23461/16293 .
 */
public class EqualSums {

    public static void main(String[] args) {
        final Scanner s = new Scanner(System.in);
        // Read number of elements to divide
        final int count = s.nextInt();
        if (count % 2 == 1) {
            throw new IllegalStateException(count + &quot; can not be divided by 2. Consider adding a 0 value.&quot;);
        }
        // Read the elements to divide
        final SortedList valueStack = new SortedList(count);
        for (int i = 0; i &lt; count; i++) {
            valueStack.add(s.nextLong());
        }

        final SortedList targetOne = new SortedList(count / 2);
        final SortedList targetTwo = new SortedList(count / 2);
        // Divide elements into two groups
        addInPairs(targetOne, targetTwo, valueStack);
        // Try to ensure groups have equal value
        retaliate(targetOne, targetTwo);

        // Output result
        System.out.println(targetOne);
        System.out.println(targetTwo);
        System.out.println(&quot;diff=&quot; + Math.abs(targetOne.getSum() - targetTwo.getSum()));
    }

    private static void addInPairs(SortedList targetOne, SortedList targetTwo, SortedList valueStack) {
        SortedList smallerTarget = targetOne;
        SortedList biggerTarget = targetTwo;
        while (!valueStack.isEmpty()) {
            // Add biggest remaining value to small target
            smallerTarget.add(valueStack.removeLast());

            // Add second biggest remaining value to big target
            biggerTarget.add(valueStack.removeLast());

            // Flip targets if roles have changed
            if (smallerTarget.getSum() &gt; biggerTarget.getSum()) {
                final SortedList temp = smallerTarget;
                smallerTarget = biggerTarget;
                biggerTarget = temp;
            }
        }

    }

    private static void retaliate(SortedList targetOne, SortedList targetTwo) {
        long difference;
        boolean changed;
        outer:
        do {
            difference = Math.abs(targetOne.getSum() - targetTwo.getSum());
            if (difference == 0) {
                return;
            }
            changed = false;
            // Try to find two values, that reduce the difference by changing them between targets
            for (Long valueOne : targetOne) {
                for (Long valueTwo : targetTwo) {
                    final Long tempOne = targetOne.getSum() + valueTwo - valueOne;
                    final Long tempTwo = targetTwo.getSum() - valueTwo + valueOne;
                    if (Math.abs(tempOne - tempTwo) &lt; difference) {
                        targetOne.remove(valueOne);
                        targetTwo.add(valueOne);
                        targetTwo.remove(valueTwo);
                        targetOne.add(valueTwo);
                        changed = true;
                        continue outer;
                    }
                }
            }
        } while (changed);
    }

    public static class SortedList extends AbstractList&lt;Long&gt; {

        private final ArrayList&lt;Long&gt; list;
        private long sum = 0;

        public SortedList(int count) {
            list = new ArrayList&lt;&gt;(count);
        }

        // the next functions access list-field directly
        @Override
        public Long get(int index) {
            return list.get(index);
        }

        @Override
        public boolean add(final Long t) {
            final int i = Collections.binarySearch(list, t);
            if (i &lt; 0) {
                // No equal element present
                list.add(-i - 1, t);
            } else {
                list.add(afterLastEqual(i, t), t);
            }
            sum += t;
            return true;
        }

        @Override
        public Long remove(int index) {
            final Long old = list.remove(index);
            sum -= old;
            return old;
        }

        @Override
        public int size() {
            return list.size();
        }

        // the next functions access list-field only through the functions above this point
        // to ensure the sum is well kept

        public long getSum() {
            return sum;
        }

        private int afterLastEqual(final int start, Object o) {
            int found = start;
            while (found &lt; size() &amp;&amp; o.equals(get(found))) {
                found++;
            }
            return found;
        }

        private int beforeFirstEqual(final int start, final Object o) {
            int found = start;
            while (found &gt;= 0 &amp;&amp; o.equals(get(found))) {
                found--;
            }
            return found;
        }

        @Override
        public int indexOf(Object o) {
            try {
                final int i = Collections.binarySearch(this, (Long) o);
                if (i &gt;= 0) {
                    return beforeFirstEqual(i, o) + 1;
                }
            } catch (ClassCastException e) {
                // Object was not instance of Long
            }
            return -1;
        }

        @Override
        public int lastIndexOf(Object o) {
            try {
                final int i = Collections.binarySearch(this, (Long) o);
                if (i &gt;= 0) {
                    return afterLastEqual(i, o) - 1;
                }
            } catch (ClassCastException e) {
                // Object was not instance of Long
            }
            return -1;
        }

        @Override
        public boolean remove(Object o) {
            if (o == null) {
                return false;
            }
            final int i = indexOf(o);
            if (i &gt;= 0) {
                remove(i);
                return true;
            }
            return false;
        }

        public Long removeLast() {
            return remove(size() - 1);
        }

        public Long removeFirst() {
            return remove(0);
        }

        @Override
        public String toString() {
            Iterator&lt;Long&gt; it = iterator();
            if (!it.hasNext()) {
                return &quot;&quot;;
            }

            StringBuilder sb = new StringBuilder();
            for (; ; ) {
                Long e = it.next();
                sb.append(e);
                if (!it.hasNext()) {
                    return sb.toString();
                }
                sb.append(' ');
            }
        }
    }
}