Polycarp likes to play with numbers. He takes some integer number $x$, writes it down on the board, and then performs with it $n - 1$ operations of the two kinds:   divide the number $x$ by $3$ ($x$ must be divisible by $3$);  multiply the number $x$ by $2$. 

After each operation, Polycarp writes down the result on the board and replaces $x$ by the result. So there will be $n$ numbers on the board after all.

You are given a sequence of length $n$ — the numbers that Polycarp wrote down. This sequence is given in arbitrary order, i.e. the order of the sequence can mismatch the order of the numbers written on the board.

Your problem is to rearrange (reorder) elements of this sequence in such a way that it can match possible Polycarp's game in the order of the numbers written on the board. I.e. each next number will be exactly two times of the previous number or exactly one third of previous number.

It is guaranteed that the answer exists.


-----Input-----

The first line of the input contatins an integer number $n$ ($2 \le n \le 100$) — the number of the elements in the sequence. The second line of the input contains $n$ integer numbers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 3 \cdot 10^{18}$) — rearranged (reordered) sequence that Polycarp can wrote down on the board.


-----Output-----

Print $n$ integer numbers — rearranged (reordered) input sequence that can be the sequence that Polycarp could write down on the board.

It is guaranteed that the answer exists.


-----Examples-----
Input
6
4 8 6 3 12 9

Output
9 3 6 12 4 8 

Input
4
42 28 84 126

Output
126 42 84 28 

Input
2
1000000000000000000 3000000000000000000

Output
3000000000000000000 1000000000000000000 



-----Note-----

In the first example the given sequence can be rearranged in the following way: $[9, 3, 6, 12, 4, 8]$. It can match possible Polycarp's game which started with $x = 9$.

Difficulty: introductory

Starter code:

Solutions:
def powof3(x):
    ans=0
    while(x%3==0):
        x=x//3
        ans+=1
    return ans


n=int(input())
a=list(map(int,input().split()))
for i in range(n):
    a[i]=[-1*powof3(a[i]),a[i]]
a.sort()
for i in range(n):
    a[i]=a[i][1]
print(*a)

n = int(input())
a = list(map(int, input().split()))
def md(x, d):
    res = 0
    dd = 1
    while x % (dd * d) == 0:
        dd *= d
        res += 1
    return res

def cmp(a, b):
    d3a = md(a, 3)
    d2a = md(a, 2)
    d3b = md(b, 3)
    d2b = md(b, 2)
    if d3a == d3b:
        return d2a < d2b
    return d3a > d3b
for i in range(n):
    for j in range(i, n):
        if cmp(a[j], a[i]):
            a[i], a[j] = a[j], a[i]
print(" ".join(map(str, a)))

n = int(input())
a = list(map(int, input().split()))
def md(x, d):
    res = 0
    dd = 1
    while x % (dd * d) == 0:
        dd *= d
        res += 1
    return res
 
def cmp(a, b):
    d3a = md(a, 3)
    d2a = md(a, 2)
    d3b = md(b, 3)
    d2b = md(b, 2)
    if d3a == d3b:
        return d2a < d2b
    return d3a > d3b
for i in range(n):
    for j in range(i, n):
        if cmp(a[j], a[i]):
            a[i], a[j] = a[j], a[i]
print(" ".join(map(str, a)))

def key(v):
    r = 0
    while v % 3 == 0:
        v //= 3
        r -= 1
    while v % 2 == 0:
        v //= 2
        r += 1
    return r
input()
print(*sorted(map(int, input().split()), key=key))


n = int(input())
a = list(map(int, input().split()))
count = []
for i in range(n):
    x = 1
    c = 0
    while (a[i] % x == 0):
        x *= 3
        c += 1
    c -= 1
    count.append([-c, a[i]])
count.sort()
for i in range(n):
    print(count[i][1], end=' ')

#!/usr/bin/env python3

import collections


def solve(n, xs):
    ys = set(xs)
    zs = collections.deque()
    zs.append(ys.pop())
    while ys:
        x = zs[len(zs) - 1]
        if x // 3 in ys:
            ys.remove(x // 3)
            zs.append(x // 3)
        elif 2 * x in ys:
            ys.remove(2 * x)
            zs.append(2 * x)
        else:
            break
    while ys:
        x = zs[0]
        if x // 2 in ys:
            ys.remove(x // 2)
            zs.appendleft(x // 2)
        elif 3 * x in ys:
            ys.remove(3 * x)
            zs.appendleft(3 * x)
        else:
            break
    return zs

def main():
    n = int(input())
    xs = [int(x) for x in input().split()]
    print(*solve(n, xs))


def __starting_point():
    main()

__starting_point()

n=int(input())
t=[*map(int,input().split())]
x=[]
for i in t:
  twoCnt,threeCnt=0,0
  tt=i
  while tt%2==0:
    tt//=2
    twoCnt+=1
  tt=i
  while tt%3==0:
    tt//=3
    threeCnt+=1
  x.append([i,twoCnt,threeCnt])
x.sort(key=lambda x:(-x[2],x[1]))
for i in x:
  print(i[0],end=' ')

n = int(input())

def k(x):
    twos = 0
    while x % 2 == 0:
        x //= 2
        twos += 1
    threes = 0
    while x % 3 == 0:
        x //= 3
        threes += 1
    return (twos, -threes)
A = sorted(map(int, input().split()), key=k)
print(' '.join(map(str, A)))


n = int(input())
a = list(map(int, input().split()))
l = [a[0]]
for i in range(1, n):
    for j in range(i, n):
        if l[-1] * 2 == a[j]:
            l += [a[j]]
            a[i], a[j] = a[j], a[i]
            break
        if (l[-1] // 3 == a[j]) and (l[-1] % 3 == 0):
            l += [a[j]]
            a[i], a[j] = a[j], a[i]
            break
        if l[0] * 3 == a[j]:
            l = [a[j]] + l
            a[i], a[j] = a[j], a[i]
            break
        if (l[0] // 2 == a[j]) and (l[0] % 2 == 0):
            l = [a[j]] + l
            a[i], a[j] = a[j], a[i]
            break
print(*l)

from collections import Counter


def read_nums():
    return [int(x) for x in input().split()]


def solve(res, num, c, n):
    res.append(num)
    c[num] -= 1
    if n == 0:
        print(' '.join([str(x) for x in res]))
        return

    if num % 3 == 0 and (num // 3) in c:
        solve(res, num//3, c, n - 1)
        res.pop()
        c[num // 3] += 1

    if (num * 2) in c:
        solve(res, num*2, c, n - 1)
        res.pop()
        c[num*2] += 1


def main():
    n = int(input())
    nums = read_nums()
    c = Counter(nums)
    res = []
    for num in nums:
        solve(res, num, c, n - 1)
        res.pop()
        c[num] += 1


def __starting_point():
    main()

__starting_point()

import sys
n=int(input())
lis=list(map(int,input().split()))
for j in range(n):
    ans=[]
    curr=lis[j]
    cnt=0
    while cnt<n:
        ans.append(curr)
        cnt+=1
        if curr*2 in lis:
            curr*=2
        elif curr//3 in lis and curr%3==0:
            curr=curr//3
        else:
            break
    if cnt==n:
        ans=[str(p) for p in ans]
        print(" ".join(ans))
        return
print(-1)


n=int(input())
a=list(map(int,input().split()))
d={}
for i in a:
    if i in d:
        d[i]+=1
    else:
        d[i]=1
mi=min(a)
arr=[mi]
prev=[mi]
while True:
    if (3*prev[-1] in d) and d[3*prev[-1]]>0:
        d[3*prev[-1]]-=1
        prev.append(3*prev[-1])
    elif prev[-1]&1==0 and prev[-1]//2 in d and d[prev[-1]//2]>0:
        d[prev[-1]//2]-=1
        prev.append(prev[-1]//2)
    else:
        break
while True:
    if 2*arr[-1] in d and d[2*arr[-1]]>0:
        d[2*arr[-1]]-=1
        arr.append(2*arr[-1])
    elif arr[-1]%3==0 and arr[-1]//3 in d and d[arr[-1]//3]>0:
        d[arr[-1]//3]-=1
        arr.append(arr[-1]//3)
    else:
        break
#print(prev,arr)
for i in range(len(prev)-1,0,-1):
    print(prev[i],end=" ")
print(*arr)


def f(x):
    nonlocal a
    if len(ans) == n:
        print(' '.join(map(str, ans)))
        return
    if x % 3 == 0 and x // 3 in a:
        ans.append(x // 3)
        f(x // 3)
        ans.pop()
    if x * 2 in a:
        ans.append(x * 2)
        f(x * 2)
        ans.pop()

n = int(input())
a = list(map(int, input().split()))

ans = []
for i in range(n):
    ans.append(a[i])
    f(a[i])
    ans.pop()


n = int(input())
s = [int(x) for x in input().split()]
d = {}

for i in range(n):
    q = s[i]
    t2 = 0
    while q % 2 == 0:
        q //= 2
        t2 += 1
    q = s[i]
    t3 = 0
    while q % 3 == 0:
        q //= 3
        t3 += 1
    d[(t3, -t2)] = s[i]

w = [i for i in d]
w.sort(reverse=1)
# print(w)
for i in range(n):
    print(d[w[i]], end=' ')


n = int(input())
inputlist = list(map(int,input().split()))
outputlist = [inputlist.pop(0)]
while len(inputlist) > 0:
	for i in range(len(inputlist)):
		if outputlist[0]*3 == inputlist[i]:
			outputlist = [inputlist.pop(i)] + outputlist
			break
		elif inputlist[i]*3 == outputlist[-1]:
			outputlist = outputlist + [inputlist.pop(i)]
			break
		elif outputlist[-1]*2 == inputlist[i]:
			outputlist = outputlist + [inputlist.pop(i)]
			break
		elif inputlist[i]*2 == outputlist[0]:
			outputlist = [inputlist.pop(i)] + outputlist 
			break
print(' '.join(list(map(str,outputlist))))

n = int(input())
a = list(map(int, input().split()))
b = []

for i in range(n):
    for k in a:
        if k*2 in a or k // 3 in a and k % 3 == 0:
             pass
        else:
            a.remove(k)
            b.append(k)
print(*reversed(b))



n = int(input())
a = input().split()
ans = []
for i in range(n):
    a[i] = int(a[i])
a.sort()
j = 0
while (len(a)>0):
    temp = []
    i = 0
    while(i<len(a)):
        if (a[i]%3!=0):
            temp.append(a[i]*pow(3,j))
            a.remove(a[i])
        else:
            a[i]//=3
            i+=1
    j+=1    
    ans.append(temp)
k = len(ans)
for i in range(k):
    for j in range(len(ans[k-i-1])):
        print(ans[k-i-1][j],end = ' ')
    
    
    
    
        
    
    
    

    
    
   



#Codeforces Round #479
#Problem D

from sys import stdin, stdout

def main():
    n = int(stdin.readline())
    a = [int(i) for i in stdin.readline().split()]
    d = dict()
    for v in a:
        v3 = 0
        vc = v
        while vc%3 == 0:
            vc = vc//3
            v3 += 1
        temp = d.get(v3, [])
        temp.append(v)
        d[v3] = temp
    k = list(d.keys())
    k.sort()
    k.reverse()
    out = []
    for i in k:
        temp = d[i]
        temp.sort()
        out += temp
    stdout.write(" ".join([str(i) for i in out]) + "\n")

main()
        


def to(a):
    s = 0
    while a % 2 == 0 and a != 0:
        s += 1
        a = a // 2
    return s

def tr(a):
    s = 0
    while a % 3 == 0 and a != 0:
        s += 1
        a = a // 3
    return s
    
         
n = int(input())
a = list(map(int, input().split()))
for i in range(n):
    for j in range(i + 1, n):
        if to(a[i]) > to(a[j]):
            a[i], a[j] = a[j], a[i]
        if tr(a[i]) < tr(a[j]):
            a[i], a[j] = a[j], a[i]
print(*a)

from heapq import heappop,heappush
n=int(input())
a=[]
c=input().split()
for i in c:
    i=int(i)
    p=0
    while not i%3:
        i//=3
        p+=1
    a+=[[] for j in range(p-len(a)+1)]
    heappush(a[p],i*3**p)
o=''
n=len(a)
for i in range(1,n+1):
    while a[n-i]:
        o+=str(heappop(a[n-i]))+' '
print(o)


import sys
input = sys.stdin.readline

N = int(input())
S = list(map(int,input().split()))

def neighbours(node,s=S):
	out = [node<<1]
	if node % 3 == 0:
		out.append(node//3)
	return set(x for x in out if x in s)

G = {}
for x in S:
	G[x] = neighbours(x)


def hamilton(G, size, pt, path=None):
	if path == None:
		path = []
	if pt not in set(path):
		path.append(pt)
		if len(path)==size:
			return path
		for pt_next in G.get(pt, []):
			res_path = [i for i in path]
			candidate = hamilton(G, size, pt_next, res_path)
			if candidate is not None:
				return candidate
for x in S:
	P = hamilton(G,N,x)
	if P:
		print(" ".join(map(str,P)))
		break

def p3(n):
    res = 0
    while n % 3 == 0:
        n //= 3
        res += 1
    return res
def p2(n):
    res = 0
    while n % 2 == 0:
        n //= 2
        res += 1
    return res
def cmp_to_key(mycmp):
    'Convert a cmp= function into a key= function'
    class K:
        def __init__(self, obj, *args):
            self.obj = obj
        def __lt__(self, other):
            return mycmp(self.obj, other.obj) < 0
        def __gt__(self, other):
            return mycmp(self.obj, other.obj) > 0
        def __eq__(self, other):
            return mycmp(self.obj, other.obj) == 0
        def __le__(self, other):
            return mycmp(self.obj, other.obj) <= 0
        def __ge__(self, other):
            return mycmp(self.obj, other.obj) >= 0
        def __ne__(self, other):
            return mycmp(self.obj, other.obj) != 0
    return K
def comp(x, y):
    return (p2(x) - p3(x)) - (p2(y) - p3(y))
n = int(input())
arr = list(map(int,input().split()))
arr = sorted(arr, key=cmp_to_key(comp))
s = str(arr[0])
for c in arr[1:]:
    s += f" {c}"
print(s)

# Project name: CF-479-D

n = int(input())
a = list(map(int, input().split()))

def func(x):
    b = list(a)
    r=[]
    for i in range(n):

        if x%3==0 and x//3 in b:
            x//=3
            b.remove(x)
            r+=[x]
        if x*2 in b:
            x*=2
            b.remove(x)
            r+=[x]
    return r


for i in a:
    if sorted( [i]+func(i)) == sorted(a):
        print (' '.join(map(str, [i]+func(i))))

n = int(input())
a = [int(i) for i in input().split()]
p = []
for i in range(n):
    for j in range(i + 1, n):
        if a[i] == a[j] * 2:
            p.append([a[i], a[j]])
        if a[j] == a[i] * 2:
            p.append([a[j], a[i]])
        if a[i] == a[j] * 3:
            p.append([a[j], a[i]])
        if a[j] == a[i] * 3:
            p.append([a[i], a[j]])
d = dict()
d[p[0][0]] = 0
for j in range(n - 1):
    for i in range(n - 1):
        if d.get(p[i][0]) != None:
            d[p[i][1]] = d[p[i][0]] - 1
        if d.get(p[i][1]) != None:
            d[p[i][0]] = d[p[i][1]] + 1
ans = []
ans_p = []
for i, j in d.items():
    ans.append(i)
    ans_p.append(j)
prov = []
for i in range(len(ans_p)):
    prov.append(ans_p[i])
prov.sort()

while ans_p != prov:
    for i in range(n - 1):
        if ans_p[i] > ans_p[i + 1]:
            ans_p[i], ans_p[i + 1] = ans_p[i + 1], ans_p[i]
            ans[i], ans[i + 1] = ans[i + 1], ans[i]
for i in range(len(ans)):
    print(ans[i], end=' ')

def three_num(n):
	result = 0
	while n % 3 == 0:
		n //= 3
		result += 1
	return result

n = int(input())
x = list(map(int, input().split()))
y = set(x)
first = x[0]
max_num = three_num(x[0])
for i in range(1, n):
	temp = three_num(x[i])
	if temp > max_num:
		max_num = temp
		first = x[i]
	elif temp == max_num and first > x[i]:
		first = x[i]
res = []
res.append(first)
y.remove(first)
for i in range(n - 1):
	if res[i] * 2 in y:
		y.remove(res[i] * 2)
		res.append(res[i] * 2)
	else:
		y.remove(res[i] // 3)
		res.append(res[i] // 3)
print(" ".join(map(str, res)))