Xenia the mathematician has a sequence consisting of n (n is divisible by 3) positive integers, each of them is at most 7. She wants to split the sequence into groups of three so that for each group of three a, b, c the following conditions held:  a < b < c;  a divides b, b divides c. 

Naturally, Xenia wants each element of the sequence to belong to exactly one group of three. Thus, if the required partition exists, then it has $\frac{n}{3}$ groups of three.

Help Xenia, find the required partition or else say that it doesn't exist.


-----Input-----

The first line contains integer n (3 ≤ n ≤ 99999) — the number of elements in the sequence. The next line contains n positive integers, each of them is at most 7.

It is guaranteed that n is divisible by 3.


-----Output-----

If the required partition exists, print $\frac{n}{3}$ groups of three. Print each group as values of the elements it contains. You should print values in increasing order. Separate the groups and integers in groups by whitespaces. If there are multiple solutions, you can print any of them.

If there is no solution, print -1.


-----Examples-----
Input
6
1 1 1 2 2 2

Output
-1

Input
6
2 2 1 1 4 6

Output
1 2 4
1 2 6

Difficulty: interview

Starter code:

Solutions:

def __starting_point():
    N = int(input())
    L = [0,0,0,0,0,0,0,0]
    inp = input()
    for i in inp.split(' '):
        L[int(i)]+=1
    it = N//3
    fnd = True
    ans = []
    for ic in range(it):
        Tl = []
        for el in range(len(L)):
            if L[el]!=0:
                if len(Tl)==0:
                    Tl.append(el)
                    L[el]-=1
                elif el%Tl[-1]==0:
                    Tl.append(el)
                    L[el]-=1
            if len(Tl)==3:
                break
        if len(Tl)==3:
            ans.append(str(Tl[0])+" "+str(Tl[1])+" "+str(Tl[2]))
        else:
            fnd=False
            break
    if fnd:
        for a in ans:
            print(a)
    else:
        print("-1")

            
    

__starting_point()

import sys
N=int(sys.stdin.readline())

A=list(map(int,sys.stdin.readline().split()))



L=[0]*8

for item in A:
    L[item]+=1

if(L[1]!=(N//3)):
    print(-1)

elif(L[7]>0 or L[5]>0):
    print(-1)

elif(L[3]+L[2]!=(N//3)):
    print(-1)

elif(L[4]+L[6]!=(N//3)):
    print(-1)

elif(L[2]<L[4]):
    print(-1)

else:
    for i in range(L[3]):
        sys.stdout.write("1 3 6\n")
    L[6]-=L[3]
    for i in range(L[6]):
        sys.stdout.write("1 2 6\n")
    for i in range(L[4]):
        sys.stdout.write("1 2 4\n")
        


from collections import defaultdict

n = int(input())
l = [int(x) for x in input().split()]

dic = defaultdict(int)
for x in l:
    dic[x] += 1

first = dic[1]
second = dic[2] + dic[3]
third = dic[4] + dic[6]
N = len(l)

if 7 in l:
    print("-1")
elif not (first == N//3 and second == N//3 and third == N//3):
    print("-1")
else:
    if dic[6] < dic[3]:
        print("-1")
    else:
        for _ in range(dic[4]):
            print("1 2 4")
        for _ in range(dic[6]-dic[3]):
            print("1 2 6")
        for _ in range(dic[3]):
            print("1 3 6")


n = int(input())
S = []
a = list(map(int, input().split()))
Ans = [0] * 10
for i in a:
    Ans[i] += 1
for i in range(1, 8):
    for j in range(i + 1, 8):
        for k in range(j + 1, 8):
            while j % i == 0 and k % j == 0 and Ans[i] > 0 and Ans[j] > 0 and Ans[k] > 0:
                S.append((i,j,k))
                Ans[i] -= 1
                Ans[j] -= 1
                Ans[k] -= 1
if len(S) == n // 3:
    for i, j, k in S:
        print(i, j, k, end= ' ')
        print()
else:
    print(-1)

n = int(input())
b = [0] * 8
a = [int(x) for x in input().split()]

for i in a:
    b[i] += 1
    
k1 = k2 = k3 = 0    
if b[5] == b[7] == 0:
    if b[3] > 0:
        b[6] -= b[3]
        b[1] -= b[3]
        k2 = b[3]
        b[3] = 0
        
    if b[6] > 0:
        k1 = b[6]
        b[1] -= b[6]
        b[2] -= b[6]
        b[6] = 0
        
    if b[4] > 0:
        k3 = b[4]
        b[1] -= b[4]
        b[2] -= b[4]
        b[4] = 0        
    if b[1] == b[2] == b[3] == b[4] == b[6] == 0:
        for i in range(k3):
            print('1 2 4')
        for i in range(k1):
            print('1 2 6') 
        for i in range(k2):
            print('1 3 6')
    else:
        print('-1')
else:
    print('-1')

n = int(input())

count = dict()
for i in range(1, 8):
    count[i] = 0
solutions = []

for i in map(int, input().split()):
    count[i] += 1

for i in range(n//3):
    if count[1] > 0:
        if count[2] > 0:
            if count[4] > 0:
                count[1] -= 1
                count[2] -= 1
                count[4] -= 1
                solutions.append([1, 2, 4])
            elif count[6] > 0:
                count[1] -= 1
                count[2] -= 1
                count[6] -= 1
                solutions.append([1, 2, 6])
        elif count[3] > 0:
            if count[6] > 0:
                count[1] -= 1
                count[2] -= 1
                count[6] -= 1
                solutions.append([1, 3, 6])

if len(solutions) == n // 3:
    for a, b, c in solutions:
        print("{} {} {}".format(a, b, c))
else:
    print(-1)

n = int(input())
a = list(map(int, input().split()))
b = [0] * 8
h = []
for i in a:
    b[i] += 1
v = min(b[1], b[2], b[4])
b[1] -= v
b[2] -= v
b[4] -= v
h.append(v)

v = min(b[1], b[3], b[6])
b[1] -= v
b[3] -= v
b[6] -= v
h.append(v)

v = min(b[1], b[2], b[6])
b[1] -= v
b[2] -= v
b[6] -= v
h.append(v)

if sum(h) * 3 < n:
    print(-1)
else:
    print('1 2 4 \n' * h[0], end = '')
    print('1 3 6 \n' * h[1], end = '')
    print('1 2 6 \n' * h[2], end = '')
    

    
    

def solve(n,items):
	grp_items = [0]*8
	for item in items:
		grp_items[item] += 1

	if (grp_items[1] == n/3 and
		grp_items[5] == 0 and
		grp_items[7] == 0 and
		grp_items[2] == (grp_items[4] + grp_items[6]-grp_items[3]) and
		grp_items[6] >= grp_items[3]):
			while grp_items[1] > 0:
				if grp_items[3] > 0:
					print('1 3 6')
					grp_items[6] -= 1
					grp_items[3] -= 1
				elif grp_items[2] > 0:
					if grp_items[6] > 0:
						print('1 2 6')
						grp_items[6] -= 1
					elif grp_items[4] > 0:
						print('1 2 4')
						grp_items[4] -= 1
					else:
						print(-1) #something wrong in algorithm
					grp_items[2] -= 1
				else:
					print(-1) #something wrong in algorithm

				grp_items[1] -= 1
	else:
		print(-1)


def __starting_point():
	n = int(input())
	items = list(map(int,input().split(' ')))
	solve(n,items)

__starting_point()

n = int(input())
arr = list(map(int, input().split()))
mp = dict()
mp[1] = 0
mp[2] = 0
mp[3] = 0
mp[4] = 0
mp[6] = 0
for num in arr:
    if num == 1:
        mp[1] = mp[1] + 1
    elif num == 2:
        mp[2] = mp[2] + 1
    elif num == 3:
        mp[3] = mp[3] + 1
    elif num == 4:
        mp[4] = mp[4] + 1
    elif num == 6:
        mp[6] = mp[6] + 1

sum0 = 0
sum1 = 0
sum2 = 0

if mp[1] != n//3:
    print(-1)
else:
    while True:
        flag = True
        if mp[2] > 0 and mp[4] > 0:
            sum0 = sum0 + 1
            flag = False
            mp[2] = mp[2] - 1
            mp[4] = mp[4] - 1
        elif mp[2] > 0 and mp[6] > 0:
            sum1 = sum1 + 1
            flag = False
            mp[2] = mp[2] - 1
            mp[6] = mp[6] - 1
        elif mp[3] > 0 and mp[6] > 0:
            sum2 = sum2 + 1
            flag = False
            mp[3] = mp[3] - 1
            mp[6] = mp[6] - 1
        if flag == True:
            break
        
    if sum0 + sum1 + sum2 != n//3:
        print(-1)
    else:
        for i in range(sum0):
            print(1, " ", 2, " ", 4)
        for i in range(sum1):
            print(1, " ", 2, " ", 6)
        for i in range(sum2):
            print(1, " ", 3, " ", 6)
        


n=int(input());
a=list(map(int,input().split()));
num=[0]*10;
for k in a:
    if(k==5 or k==7):
        print(-1);
        return;
    num[k]+=1;
p=min(num[1],num[2],num[4]);
num[1]-=p;num[2]-=p;num[4]-=p;
q=min(num[1],num[3],num[6]);
num[1]-=q;num[3]-=q;num[6]-=q;
k=min(num[1],num[2],num[6]);
num[1]-=k;num[2]-=k;num[6]-=k;
for i in range(7):
    if(num[i+1]):
        print(-1);
        return;
for i in range(p):
    print(1,2,4);
for i in range(q):
    print(1,3,6);
for i in range(k):
    print(1,2,6);

a=[0 for i in range(8)]
N=int(input())
b=list(map(int, input().split()))
for k in range(N):
    a[b[k-1]]=a[b[k-1]]+1;
if a[5] or a[7]:
    print(-1)
    return
A,C=a[4],a[3]
B=a[6]-C
if A>=0 and B>=0 and C>=0 and A+B==a[2] and A+B+C==a[1]:
    for i in range(A):
        print("1 2 4")
    for i in range(B):
        print("1 2 6")
    for i in range(C):
        print("1 3 6")
else: print(-1)

n=int(input())
a=list(map(int,input().split()))
a.sort()
n=n/3
ok=1
if(a.count(1)!=n): ok=0
if(a.count(5)+a.count(7)>0): ok=0

p=a.count(2)-a.count(4)

if p<0:ok=0
if p+a.count(3)!=a.count(6):ok=0
if ok==0:
    print(-1)
else:
    t4=a.count(4)
    t26=p
    t36=a.count(6)-t26
    for i in range(0,t4):
        print(1,2,4)

    for i in range(0,t26):
        print(1,2,6)
    for i in range(0,t36):
        print(1,3,6)

        


count = {}
ans = []
def mx(a,b,c):
    ans.append((a,b,c))
    count[a]-=1
    count[b]-=1
    count[c]-=1
n = int(input())

nums = list(map(int, input().split()))

if 5 in nums or 7 in nums or nums.count(1) != n // 3:
    print(-1)
else:
    for i in [1,2,3,4,6]:
        count[i] = nums.count(i)
    while count[2] > 0 and count[4]> 0:
        mx(1,2,4)
    while count[2] > 0 and count[6] > 0:
        mx(1,2,6)
    while count[3] > 0 and count[6] > 0:
        mx(1,3,6)
if sum(count.values())>0:
    print(-1)
else:
    for a,b,c in ans:
        print(a,b,c)
        


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

c = [0] * 8
for i in range(n):
  c[a[i]] += 1
  
x = min(c[1], c[2], c[4])
c[1] -= x
c[2] -= x
c[4] -= x
y = min(c[1], c[2], c[6])
c[1] -= y
c[2] -= y
c[6] -= y
z = min(c[1], c[3], c[6])

if 3 * (x + y + z) != n:
  print(-1)
else:
  for i in range(x):
    print(1, 2, 4)
  for i in range(y):
    print(1, 2, 6)
  for i in range(z):
    print(1, 3, 6)

n = int(input())
x = list(map(int, input().split()))
a = 0
b = 0
c = 0
d = 0
e = 0
for i in range(n):
    if x[i] == 1:
        a += 1
    if x[i] == 2:
        b += 1
    if x[i] == 3:
        c += 1
    if x[i] == 4:
        d += 1
    if x[i] == 6:
        e += 1
    if x[i] == 5 or x[i] == 7:
        print(-1)
        return
if a != b + c or b + c != d + e or c > e:
    print(-1)
    return
for i in range(d):
    print(1, 2, 4)
b -= d
for i in range(b):
    print(1, 2, 6)
for i in range(c):
    print(1, 3, 6)


def f():
    n = int(input()) // 3
    t = input()
    if '5' in t: return -1
    a = t.count('1')
    if a != n: return -1
    b = t.count('2')
    c = t.count('3')
    if b + c != n: return -1
    d = t.count('4')
    if d > b: return -1
    f = t.count('6')
    if f < c: return -1
    return '1 2 4\n' * d + '1 3 6\n' * c + '1 2 6\n' * (n - d - c)
print(f())

def main(n, nums):
	ex = n//3
	if 5 in nums or 7 in nums or nums.count(1)!=ex:
		return -1
	else:
		s = ''
		q = nums.count(4)
		w = nums.count(6)
		e = nums.count(3)
		r = nums.count(2)
		if r!=q+w-e or w!=e+r-q or e>w or q>r:
			return -1
		s+='1 2 4\n'*q
		s+='1 2 6\n'*(ex-q-e)
		s+='1 3 6\n'*e
		return s[:-1]

def init():
	n = int(input())
	nums = list(map(int, input().split()))

	print(main(n, nums))

init()

n=int(input())
p=[7]
r=[]
cnt=0
for i in range(0,8):
    p.append(0)
a=list(map(int,input().split()))
for i in a:
    p[i]=p[i]+1
if(p[5]>0 or p[7]>0):
    print("-1")
    return
if(p[1]+p[2]<n/3):
    print("-1")
    return
while(p[1]>0 and p[3]>0 and p[6]>0):
    if(p[3]>0 and p[6]>0):
        r.append("1 3 6")
        p[1]=p[1]-1
        p[3]=p[3]-1
        p[6]=p[6]-1
        cnt=cnt+1
while(p[1]>0 and p[2]>0 and p[4]>0):
    if(p[2]>0 and p[4]>0):
        r.append("1 2 4")
        p[1]=p[1]-1
        p[4]=p[4]-1
        p[2]=p[2]-1
        cnt=cnt+1
while(p[1]>0 and p[2]>0 and p[6]>0):
    if(p[2]>0 and p[6]>0):
        r.append("1 2 6")
        p[1]=p[1]-1
        p[2]=p[2]-1
        p[6]=p[6]-1
        cnt=cnt+1
if(cnt!=n/3):
    print("-1")
    return
else:
    for i in r:
        print(i)
return


n = int(input())
a = list(map(int, input().split()))
c = [0]*8
for i in range(1, 8):
    c[i] = a.count(i)
if c[5] or c[7] or c[1] != n//3 or c[3] > c[6] or c[4] > c[2] or c[6]-c[3] != c[2]-c[4]:
    print(-1)
else:
    for i in range(c[4]):
        print('1 2 4')
    for i in range(c[2]-c[4]):
        print('1 2 6')
    for i in range(c[3]):
        print('1 3 6')



import sys
N=int(sys.stdin.readline())

A=list(map(int,sys.stdin.readline().split()))



L=[0]*8

for item in A:
    L[item]+=1

if(L[1]!=(N//3)):
    print(-1)

elif(L[7]>0 or L[5]>0):
    print(-1)

elif(L[3]+L[2]!=(N//3)):
    print(-1)

elif(L[4]+L[6]!=(N//3)):
    print(-1)

elif(L[2]<L[4]):
    print(-1)

else:
    for i in range(L[3]):
        sys.stdout.write("1 3 6\n")
    L[6]-=L[3]
    for i in range(L[6]):
        sys.stdout.write("1 2 6\n")
    for i in range(L[4]):
        sys.stdout.write("1 2 4\n")
        


n = int(input())
a = list(map(int,input().split()))
c = [0]*8
for i in a:
    c[i]+=1
if c[5] or c[7]:
    print(-1)
    return
t1 = c[3]
c[3] = 0
c[1] -= t1
c[6] -= t1
t2 = c[6]
c[1] -= t2
c[6] = 0
c[2] -= t2
t3 = c[4]
c[4] = 0
c[2] -= t3
c[1] -= t3
if c.count(0) != 8 or t1<0 or t2<0 or t3<0:
    print(-1)
else:
    for i in range(t1):
        print('1 3 6')
    for i in range(t2):
        print('1 2 6')
    for i in range(t3):
        print('1 2 4')

n = int(input())
a = list(map(int,input().split()))
cnt = [0]*8

for i in a:
    cnt[i] += 1
ans = 1
if cnt[5]>0 or cnt[7]>0:
    ans = 0
if cnt[4] > cnt[2]:
    ans = 0
if cnt[1] != n/3:
    ans = 0
if cnt[2] - cnt[4] + cnt[3] != cnt[6]:
    ans = 0

if ans == 0:
    print('-1\n')
else:
    while cnt[4]:
        print('1 2 4\n')
        cnt[2]=cnt[2]-1
        cnt[4]=cnt[4]-1
    while cnt[2]:
        print('1 2 6\n')
        cnt[2]=cnt[2]-1
    while cnt[3]:
        print('1 3 6\n')
        cnt[3]=cnt[3]-1


n=int(input())
a=list(map(int,input().split()))
t=[0]*8
for x in a:
    t[x]+=1
if t[5]>0 or t[7]>0 or t[1]*3<n:
    print(-1)
else:
    a=t[4]
    c=t[3]
    b=t[2]-a
    if b<0 or (a+b+c)!=t[1] or (b+c)!=t[6]:
        print(-1)
        return
    for i in range(a):
        print('1 2 4')
    for i in range(b):
        print('1 2 6')
    for i in range(c):
        print('1 3 6')


n = input()
a = [int(i) for i in input().split()]
g = 0
k = [0] * 7
flag = False
k[0] = a.count(1)
k[1] = a.count(2)
k[2] = a.count(3)
k[3] = a.count(4)
k[4] = a.count(5)
k[5] = a.count(6)
k[6] = a.count(7)
if (k[0] == k[1] + k[2] == k[3] + k[5]) and (k[4] + k[6] == 0) and (k[2] <= k[5]) and (k[3] <= k[1]):
    flag = True
else:
    print(-1)
if flag:
    for i in range(k[0]):
        print(1, end= ' ')
        if k[2] > 0:
            print(3, end= ' ')
            print(6)
            k[5] -= 1
            k[2] -= 1
        else:
            print(2, end= ' ')
            if k[5] > 0:
                print(6)
                k[5] -= 1
            else:
                print(4)

c = [0] * 8
n = int(input())
for x in input().split():
    c[int(x)] += 1
if c[5] > 0 or c[7] > 0 or c[1] != c[2] + c[3] or c[1] != c[4] + c[6] or c[4] > c[2]:
    print(-1)
else:
    for i in range(c[4]):
        print('1 2 4')
    for i in range(c[2] - c[4]):
        print('1 2 6')
    for i in range(c[3]):
        print('1 3 6')