Vasya has gotten interested in programming contests in TCMCF+++ rules. On the contest n problems were suggested and every problem had a cost — a certain integral number of points (perhaps, negative or even equal to zero). According to TCMCF+++ rules, only accepted problems can earn points and the overall number of points of a contestant was equal to the product of the costs of all the problems he/she had completed. If a person didn't solve anything, then he/she didn't even appear in final standings and wasn't considered as participant. Vasya understood that to get the maximal number of points it is not always useful to solve all the problems. Unfortunately, he understood it only after the contest was finished. Now he asks you to help him: find out what problems he had to solve to earn the maximal number of points.

Input

The first line contains an integer n (1 ≤ n ≤ 100) — the number of the suggested problems. The next line contains n space-separated integers ci ( - 100 ≤ ci ≤ 100) — the cost of the i-th task. The tasks' costs may coinсide.

Output

Print space-separated the costs of the problems that needed to be solved to get the maximal possible number of points. Do not forget, please, that it was necessary to solve at least one problem. If there are several solutions to that problem, print any of them.

Examples

Input

5
1 2 -3 3 3


Output

3 1 2 3 


Input

13
100 100 100 100 100 100 100 100 100 100 100 100 100


Output

100 100 100 100 100 100 100 100 100 100 100 100 100 


Input

4
-2 -2 -2 -2


Output

-2 -2 -2 -2

Difficulty: MEDIUM
Tags: Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
import sys
input = sys.stdin.readline
n = int(input())
s = list(map(int, input().split()))
s.sort()
s.reverse()
num_manfi = 0
num_sefr = 0
flag = 0
for i in s:
	if i > 0:
		print(i, end=' ')
		flag = 1
	elif i == 0:
		num_sefr += 1
	else:
		num_manfi += 1
num_manfi -= num_manfi % 2
s.reverse()
for i in range(num_manfi):
	print(s[i], end=' ')
if not flag and num_manfi <= 0 and (num_sefr > 0):
	print(0, end=' ')
	exit()
if not flag and num_sefr <= 0 and (num_manfi <= 0):
	print(s[0])
	exit()


a = int(input())
t = list(map(int, input().split()))
ne = []
po = []
for s in t:
	if s < 0:
		ne.append(s)
	elif s > 0:
		po.append(s)
ne.sort()
if len(po) == 0 and len(ne) == 0:
	if 0 in t:
		print(0)
elif len(ne) % 2 == 0:
	print(*ne + po)
elif len(ne) == 1:
	if len(po) > 0:
		print(*po)
	elif 0 in t:
		print(0)
	else:
		print(*ne)
else:
	print(*ne[:-1] + po)


(n, a) = (int(input()), list(map(int, input().split())))
(an, ap) = (sorted((x for x in a if x < 0)), [x for x in a if x > 0])
if n > 1 and len(an) % 2:
	an.pop()
print(' '.join(map(str, ap + an)) if ap or an else 0)


import sys
input = sys.stdin.readline
n = int(input())
nums = list(map(int, input().split()))
nums.sort()
res = []
i = 0
while i < n:
	if nums[i] < 0 and i < n - 1 and (nums[i + 1] < 0):
		res.append(nums[i])
		res.append(nums[i + 1])
		i += 2
	elif nums[i] == 0:
		i += 1
	elif nums[i] > 0:
		res.append(nums[i])
		i += 1
	else:
		i += 1
if res:
	print(*res)
else:
	print(nums[-1])


n = int(input())
a = list(map(int, input().split()))
b = []
c = []
for x in a:
	if x > 0:
		b.append(x)
	elif x < 0:
		c.append(x)
if len(c) % 2 != 0:
	c = sorted(c)[:-1]
b += c
if len(b) == 0:
	print(*a)
else:
	print(*b)


b = []
k = 0
imax = -101
n = input()
a = [int(s) for s in input().split()]
if len(a) == 1:
	print(a[0])
	exit()
if len(a) == a.count(0):
	print(0)
	exit()
for i in range(len(a)):
	if a[i] < 0:
		k += 1
		if a[i] > imax:
			imax = a[i]
if k % 2 == 0:
	for i in range(len(a)):
		if a[i] != 0:
			b.append(a[i])
	if b == []:
		print(max(a))
		exit()
	for i in range(len(b)):
		print(b[i], end=' ')
else:
	for i in range(len(a)):
		if a[i] != 0 and (not i == a.index(imax)):
			b.append(a[i])
	if b == []:
		print(max(a))
		exit()
	for i in range(len(b)):
		print(b[i], end=' ')


n = int(input())
costs = list(map(int, input().split()))
(negative, positive) = ([], [])
for cost in costs:
	if cost < 0:
		negative.append(cost)
	elif cost > 1:
		positive.append(cost)
negative.sort()
if len(negative) % 2 == 1:
	negative = negative[:-1]
result = negative + sorted(positive)
if len(result) == 0:
	result = sorted(costs)[-1:]
print(' '.join(map(str, result)))


n = int(input())
l = list(map(int, input().split()))
x = []
s = ''
for i in l:
	if i < 0:
		x.append(i)
if len(x) % 2 == 0:
	for i in l:
		if i != 0:
			s += str(i)
			s += ' '
	if s == '':
		s = str(max(l)) + ' '
	print(s[:-1])
else:
	c = 0
	for i in l:
		if (i != max(x) or c == 1) and i != 0:
			s += str(i)
			s += ' '
		elif i == max(x):
			c += 1
	if s == '':
		s = str(max(l)) + ' '
	print(s[:-1])


def TCMCF():
	num = int(input())
	costs = [int(i) for i in input().split()]
	if num == 1:
		print(costs[0])
	elif num == 2:
		if costs[0] < 0:
			if costs[1] < 0:
				print(costs[0], costs[1])
			else:
				print(costs[1])
		elif costs[1] < 0:
			print(costs[0])
		elif costs[0] == 0:
			print(costs[1])
		elif costs[1] == 0:
			print(costs[0])
		else:
			print(costs[0], costs[1])
	else:
		negative_numbers = []
		for i in costs:
			if i < 0:
				negative_numbers.append(i)
		if costs.count(0) == len(costs) - 1:
			if negative_numbers == 1:
				print(0)
			else:
				for i in costs:
					if i != 0:
						print(i)
		else:
			for i in costs:
				if i == 0:
					costs.remove(i)
			if len(negative_numbers) % 2 == 1:
				costs.remove(max(negative_numbers))
			for i in costs:
				if abs(i) < 1:
					costs.remove(i)
			print(' '.join([str(i) for i in costs]))
TCMCF()


n = int(input())
c = list(sorted(map(int, input().split())))
neg = []
ans = []
zero = 0
for x in c:
	if x > 0:
		ans.append(x)
	elif x < 0:
		neg.append(x)
	else:
		zero += 1
m = len(neg) // 2
for i in range(2 * m):
	ans.append(neg[i])
if len(ans) == 0 and zero > 0:
	ans.append(0)
elif len(ans) == 0 and len(neg) > 0:
	ans.append(neg[0])
print(' '.join(map(str, ans)))


n = int(input())
p = []
q = []
z = 0
for x in map(int, input().split()):
	if x > 0:
		p += (x,)
	elif x < 0:
		q += (x,)
	else:
		z += 1
if p:
	if q:
		if len(q) % 2:
			p += sorted(q)[:-1]
		else:
			p += q
	print(' '.join(map(str, p)))
elif len(q) > 1:
	q = sorted(q)
	if len(q) % 2:
		q.pop()
	print(' '.join(map(str, q)))
elif z:
	print(0)
else:
	print(q[0])


from collections import Counter as cnt, defaultdict as dic
iin = lambda : int(input())
lin = lambda : list(map(int, input().rstrip().split()))
TEST_CASES = False

def main():
	n = iin()
	a = lin()
	(p, neg, z) = ([], [], 0)
	for i in a:
		if i > 0:
			p.append(i)
		elif i < 0:
			neg.append(i)
		else:
			z += 1
	if z == len(a):
		print(0)
	elif len(p) == 0 and len(neg) == 1:
		if z == 0:
			print(*neg)
		else:
			print(0)
	elif len(neg) % 2 != 0:
		neg.sort()
		neg.pop()
		p.extend(neg)
	else:
		p.extend(neg)
	print(*p)
if not TEST_CASES:
	main()
else:
	[main() for _ in range(int(input()))]


n = int(input())
lstarr = list(map(int, input().split()))
if n == 1:
	print(*lstarr)
	exit()
neg = []
zero = 0
pos = []
mx = 0
for i in lstarr:
	if i > 0:
		pos.append(i)
	elif i < 0:
		neg.append(i)
	else:
		zero += 1
if zero == n:
	print(0)
else:
	neg = sorted(neg)
	if len(neg) % 2 == 0:
		neg = neg + pos
		print(*neg)
	else:
		del neg[-1]
		neg = neg + pos
		if neg == []:
			print(0)
		else:
			print(*neg)


n = int(input())
a = list(map(int, input().split()))
pos = []
neg = []
z = 0
for i in range(n):
	if a[i] > 0:
		pos.append(a[i])
	elif a[i] < 0:
		neg.append(a[i])
	else:
		z += 1
m = len(neg)
neg.sort()
if m % 2:
	m -= 1
for i in range(m):
	pos.append(neg[i])
if len(pos) > 0:
	for i in range(len(pos)):
		print(pos[i], end=' ')
elif z:
	print(0)
else:
	print(neg[0])


n = int(input())
c = list(map(int, input().split()))
pos = 0
neg = 0
l_pos = []
l_neg = []
for item in c:
	if item < 0:
		neg += 1
		l_neg.append(item)
	elif item > 0:
		pos += 1
		l_pos.append(item)
if len(c) == 1 or (len(set(c)) == 1 and c[0] == 0):
	print(c[0])
elif len(c) == 2 and max(c) == 0:
	print(0)
elif neg % 2 == 0:
	for item in c:
		if item != 0:
			print(item, end=' ')
else:
	for item in l_pos:
		print(item, end=' ')
	l_neg.sort()
	for i in range(len(l_neg) - 1):
		print(l_neg[i], end=' ')


try:
	n = int(input())
	arr = list(map(int, input().split()))
	positive = [item for item in arr if item > 0]
	negative = [item for item in arr if item < 0]
	zero = [item for item in arr if item == 0]
	negative.sort(reverse=True)
	length = len(negative)
	z_length = len(zero)
	if length > 1:
		if length % 2 == 0:
			ans = positive + negative
			print(*ans)
		else:
			ans = positive + negative[1:]
			print(*ans)
	elif length == 1:
		if len(positive) > 0:
			print(*positive)
		elif z_length != 0:
			print(0)
		else:
			print(*negative)
	elif len(positive) > 0:
		print(*positive)
	elif z_length != 0:
		print(0)
except e:
	pass


import sys
input = sys.stdin.readline
n = int(input())
l = input().split()
li = [int(i) for i in l]
if n == 1:
	print(li[0])
	quit()
neg = []
pos = []
for i in range(n):
	if li[i] > 0:
		pos.append(li[i])
	elif li[i] < 0:
		neg.append(li[i])
if len(pos) == 0 and len(neg) <= 1:
	print(0)
	quit()
for i in pos:
	print(i, end=' ')
neg.sort()
neg.reverse()
z = len(neg)
if z % 2 == 0:
	for i in neg:
		print(i, end=' ')
else:
	for i in range(1, z):
		print(neg[i], end=' ')


n = int(input())
lst = [*map(int, input().split())]
(a, b) = ([], [])
for (i, x) in enumerate(lst):
	if x > 0:
		a.append(x)
	if x < 0:
		b.append(x)
b.sort()
if len(b) % 2 == 0:
	a.extend(b)
else:
	a.extend(b[:-1])
if a == []:
	print(max(lst))
else:
	print(*a)


int(input())
aList = sorted([int(x) for x in input().split()])
bList = []
needSecond = False
thing = 0
for i in aList:
	if i < 0 and (not needSecond):
		thing = i
		needSecond = True
	elif i < 0:
		bList.append(thing)
		bList.append(i)
		needSecond = False
	elif i > 0:
		bList.append(i)
if len(bList) == 0:
	print(max(aList))
else:
	print(' '.join([str(x) for x in bList]))


from bisect import bisect_left as bl
n = int(input())
if n == 1:
	print(input())
else:
	a = list(map(int, input().split()))
	a.sort()
	if bl(a, 0) % 2 == 1:
		if a[bl(a, 0) - 1] < 0:
			a.remove(a[bl(a, 0) - 1])
	q = len(a)
	while 0 in a and q > 1:
		a.remove(0)
		q -= 1
	print(*a)


import bisect
from itertools import accumulate
import os
import sys
import math
from decimal import *
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

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

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		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))

def input():
	return sys.stdin.readline().rstrip('\r\n')

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def SieveOfEratosthenes(n):
	prime = []
	primes = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if primes[p] == True:
			prime.append(p)
			for i in range(p * p, n + 1, p):
				primes[i] = False
		p += 1
	return prime
n = int(input())
a = list(map(int, input().split()))
greater = []
less = []
zero = []
for i in range(0, len(a)):
	if a[i] > 0:
		greater.append(a[i])
	elif a[i] == 0:
		zero.append(a[i])
	else:
		less.append(a[i])
ans = []
less.sort()
if len(greater) == 0 and len(less) == 1:
	ans.append(less[-1])
	if len(zero) > 0:
		ans.append(0)
	print(*ans)
	exit()
if len(greater) == 0 and len(less) == 0:
	if len(zero) > 0:
		ans.append(0)
		print(*ans)
		exit()
for i in range(0, len(greater)):
	ans.append(greater[i])
if len(less) % 2 == 0:
	ans = ans + less
else:
	less = less[:-1]
	for i in range(0, len(less)):
		ans.append(less[i])
print(*ans)