Problem: Vitaly has an array of n distinct integers. Vitaly wants to divide this array into three non-empty sets so as the following conditions hold: 

  1. The product of all numbers in the first set is less than zero ( < 0). 
  2. The product of all numbers in the second set is greater than zero ( > 0). 
  3. The product of all numbers in the third set is equal to zero. 
  4. Each number from the initial array must occur in exactly one set. 



Help Vitaly. Divide the given array.

Input

The first line of the input contains integer n (3 ≤ n ≤ 100). The second line contains n space-separated distinct integers a1, a2, ..., an (|ai| ≤ 103) — the array elements.

Output

In the first line print integer n1 (n1 > 0) — the number of elements in the first set. Then print n1 numbers — the elements that got to the first set.

In the next line print integer n2 (n2 > 0) — the number of elements in the second set. Then print n2 numbers — the elements that got to the second set.

In the next line print integer n3 (n3 > 0) — the number of elements in the third set. Then print n3 numbers — the elements that got to the third set.

The printed sets must meet the described conditions. It is guaranteed that the solution exists. If there are several solutions, you are allowed to print any of them.

Examples

Input

3
-1 2 0


Output

1 -1
1 2
1 0


Input

4
-1 -2 -3 0


Output

1 -1
2 -3 -2
1 0

Solution (in PYTHON):

Solution:
from __future__ import division, print_function


def main():
    # Template 1.0
    import sys, re, math
    from collections import deque, defaultdict, Counter, OrderedDict
    from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, floor
    from heapq import heappush, heappop, heapify, nlargest, nsmallest
    def STR(): return list(input())

    def INT(): return int(input())

    def MAP(): return map(int, input().split())

    def LIST(): return list(map(int, input().split()))

    def list2d(a, b, c): return [[c] * b for i in range(a)]

    def sortListWithIndex(listOfTuples, idx):   return (sorted(listOfTuples, key=lambda x: x[idx]))

    def sortDictWithVal(passedDic):
        temp = sorted(passedDic.items(), key=lambda kv: (kv[1], kv[0]))
        toret = {}
        for tup in temp:
            toret[tup[0]] = tup[1]
        return toret

    def sortDictWithKey(passedDic):
        return dict(OrderedDict(sorted(passedDic.items())))

    INF = float('inf')
    mod = 10 ** 9 + 7



    n = INT()

    a = LIST()

    p,q,r = [],[],[]

    for el in a:
        if(el==0):
            r.append(el)
        elif(el<0):
            p.append(el)
        else:
            q.append(el)
    if(len(q)==0):
        q.append(p[0])
        q.append(p[1])
        p.pop(0)
        p.pop(0)

    if(len(p)%2==0):
        r.append(p[0])
        p.pop(0)

    print(len(p), end = " ")
    print(*p)
    print(len(q), end=" ")
    print(*q)
    print(len(r), end = " ")
    print(*r)


######## Python 2 and 3 footer by Pajenegod and c1729

# Note because cf runs old PyPy3 version which doesn't have the sped up
# unicode strings, PyPy3 strings will many times be slower than pypy2.
# There is a way to get around this by using binary strings in PyPy3
# but its syntax is different which makes it kind of a mess to use.

# So on cf, use PyPy2 for best string performance.

py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip

    range = xrange

import os, sys
from io import IOBase, BytesIO

BUFSIZE = 8192


class FastIO(BytesIO):
    newlines = 0

    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = "x" in file.mode or "w" in file.mode
        self.write = super(FastIO, self).write if self.writable else None

    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0, 2), super(FastIO, self).write(s))[0])
        return s

    def read(self):
        while self._fill(): pass
        return super(FastIO, self).read()

    def readline(self):
        while self.newlines == 0:
            s = self._fill();
            self.newlines = s.count(b"\n") + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.getvalue())
            self.truncate(0), self.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            self.write = lambda s: self.buffer.write(s.encode('ascii'))
            self.read = lambda: self.buffer.read().decode('ascii')
            self.readline = lambda: self.buffer.readline().decode('ascii')


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip('\r\n')

# Cout implemented in Python
import sys


class ostream:
    def __lshift__(self, a):
        sys.stdout.write(str(a))
        return self


cout = ostream()
endl = '\n'


# Read all remaining integers in stdin, type is given by optional argument, this is fast
def readnumbers(zero=0):
    conv = ord if py2 else lambda x: x
    A = [];
    numb = zero;
    sign = 1;
    i = 0;
    s = sys.stdin.buffer.read()
    try:
        while True:
            if s[i] >= b'0'[0]:
                numb = 10 * numb + conv(s[i]) - 48
            elif s[i] == b'-'[0]:
                sign = -1
            elif s[i] != b'\r'[0]:
                A.append(sign * numb)
                numb = zero;
                sign = 1
            i += 1
    except:
        pass
    if s and s[-1] >= b'0'[0]:
        A.append(sign * numb)
    return A


if __name__ == "__main__":
    main()