Han Solo and Chewbacca start a space journey to planet Naboo on the Millennium Falcon. During the journey they land at a mysterious planet with high gravity where they find n diamond stones scattered all around. All the stones are of same weight. Each stone has a value according to its purity which can be detected by a special device. They choose to divide the stones fairly among themselves in two halves so that they carry almost equal weights such that the difference between the value of two halves is as small as possible. If n is even, then sizes of two halves must be strictly n/2 and if n is odd, then size of one half must be (n-1)/2 and size of the other half must be (n+1)/2. Given the value of stones, help them to divide the stones among themselves.

-----Input-----
First line consists of an integer n which denotes the number of stones.Second line consists of n space separated integers denoting the value of the stones.

-----Output-----
First line consists of the values of the stones assigned to Han Solo.Second line consists of the values of the stones assigned to Chewbacca.Assume that the set containing the first value in the input is always assigned to Han Solo.Also the values in the output sets must follow the same ordering as the input.

-----Constraints-----
The number of stones can range from 2 to 99.The values of the stones vary from 1 to 10^4.

-----Example-----
Input:
7
1 2 3 4 5 6 7

Output:
1 2 4 7
3 5 6

-----Explanation-----
These 7 values must be separated into 2 sets of sizes 3 and 4.In this case, it is possible to form two sets (1,2,4,7) & (3,5,6) of equal size.The set containing the first value (i.e.) 1 must be assigned to Han Solo and the elements of the output sets have the same order as the input.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = "s,n,s1,lis,new1=[],[],[],[],[]\nimport itertools\nq = int(input())\ns.append(input().split(' '))\ns1 = list([list(map(int,x)) for x in s])\nsum1 = sum(s1[0])\nif len(s1[0])%2!=0 :\n z = (len(s1[0])+1)//2\n n = list(itertools.combinations(s1[0],z))\n for j in range(len(n)) :\n   x = sum(n[j])\n   if x==sum1//2 :\n    lis = n[j]\n    break\n new1 = list(lis)\n sum2 = sum(new1)\n for j in range(len(lis)) :\n    y = lis[j]\n    s1[0].remove(y)\n sum3=sum(s1[0])\n if sum3>sum2 :\n  print(' '.join(map(str,s1[0])))\n  print(' '.join(map(str,new1)))\n else :\n  print(' '.join(map(str,new1)))\n  print(' '.join(map(str,s1[0])))\nelse :\n z = len(s1[0])//2\n n = list(itertools.combinations(s1[0],z))\n for j in range(len(n)) :\n   x = sum(n[j])\n   if x==sum1//2 :\n    lis = n[j]\n    break\n   #print lis,len(lis)\n new1 = list(lis)\n sum2 = sum(new1)\n for j in range(len(lis)) :\n    y = lis[j]\n    s1[0].remove(y)\n sum3 = sum(s1[0])\n if sum3>sum2  :\n  print(' '.join(map(str,s1[0])))\n  print(' '.join(map(str,new1)))\n else :\n  print(' '.join(map(str,new1)))\n  print(' '.join(map(str,s1[0])))\n\n  \n"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 14963