There is a programing contest named SnakeUp, 2n people want to compete for it. In order to attend this contest, people need to form teams of exactly two people. You are given the strength of each possible combination of two people. All the values of the strengths are distinct.

Every contestant hopes that he can find a teammate so that their team’s strength is as high as possible. That is, a contestant will form a team with highest strength possible by choosing a teammate from ones who are willing to be a teammate with him/her. More formally, two people A and B may form a team if each of them is the best possible teammate (among the contestants that remain unpaired) for the other one. 

Can you determine who will be each person’s teammate?


-----Input-----

There are 2n lines in the input. 

The first line contains an integer n (1 ≤ n ≤ 400) — the number of teams to be formed.

The i-th line (i > 1) contains i - 1 numbers a_{i}1, a_{i}2, ... , a_{i}(i - 1). Here a_{ij} (1 ≤ a_{ij} ≤ 10^6, all a_{ij} are distinct) denotes the strength of a team consisting of person i and person j (people are numbered starting from 1.)


-----Output-----

Output a line containing 2n numbers. The i-th number should represent the number of teammate of i-th person.


-----Examples-----
Input
2
6
1 2
3 4 5

Output
2 1 4 3

Input
3
487060
3831 161856
845957 794650 976977
83847 50566 691206 498447
698377 156232 59015 382455 626960

Output
6 5 4 3 2 1



-----Note-----

In the first sample, contestant 1 and 2 will be teammates and so do contestant 3 and 4, so the teammate of contestant 1, 2, 3, 4 will be 2, 1, 4, 3 respectively.

Difficulty: interview

Starter code:

Solutions:
n = int(input())

a = []
for i in range(2*n - 1):
    a.append([int(c) for c in input().split()])


c = []
for i in range(len(a)):
    for j in range(len(a[i])):
        c.append([a[i][j], i+1, j])

c.sort(reverse=True)
used = set()
res = [0]*2*n
for cc in c:
    if not cc[1] in used and not cc[2] in used:
        res[cc[1]] = cc[2] + 1
        res[cc[2]] = cc[1] + 1
        used.add(cc[1])
        used.add(cc[2])

print(' '.join(str(r) for r in res))


n = int(input())
nums = []
people = [True]*2*n
pairs = [-1]*2*n
for i in range(1, 2*n):
	i_nums = list(map(int, input().split()))
	# print(i_nums)
	nums += list(zip(i_nums, [i]*i, range(i)))
nums.sort(key=lambda x: x[0], reverse=True)
for num, i, j in nums:
	if people[i] and people[j]:
		people[i] = people[j] = False
		pairs[i] = str(j + 1)
		pairs[j] = str(i + 1)
print(" ".join(pairs))

n = int(input())
p = [-1] * 2 * n
k = []
for i in range(2 * n - 1):
    a = list(map(int, input().split()))
    for t in range(i + 1):
        k.append([a[t], i + 1, t])
k.sort()
for i in range(len(k) - 1, -1, -1):
    if p[k[i][1]] == -1 and p[k[i][2]] == -1:
        p[k[i][1]] = k[i][2] + 1
        p[k[i][2]] = k[i][1] + 1
print(*p)



n = int(input())

strs = [list(map(int, input().split())) for _ in range(2*n-1)]
entries = sorted(((v, i, j) for i, row in enumerate(strs)
                  for j, v in enumerate(row)), reverse=True)
ans = [-1] * (2*n)

for v, i, j in entries:
    i += 1
    if ans[i] != -1 or ans[j] != -1:
        continue
    ans[i] = j+1
    ans[j] = i+1

print(' '.join(map(str, ans)))


#import sys
#sys.stdin = open("python/in", "r")
#from collections import defaultdict
#import numpy as np
#import array as rr
#arr = rr.array('q')

n = int(input())
#n, m = [int (i) for i in input().split(" ")]
ans = {}
arr = []
for con in range(1, 2*n):
    str = [int (i) for i in input().split(" ")]
    arr.extend( [(str[i], i, con ) for i in range(len(str))])
arr.sort()
arr.reverse()
for s, a, b in arr:
    if a in ans.keys() or b in ans.keys():
        continue
    ans[a] = b+1
    ans[b] = a+1

for i in range(2*n):
    print(ans[i], end=' ')
    

#!/usr/bin/env python
# 579B_member.py - Codeforces.com/problemset/problem/579/B by Sergey 2015

import unittest
import sys

###############################################################################
# Member Class (Main Program)
###############################################################################


class Member:
    """ Member representation """

    def __init__(self, test_inputs=None):
        """ Default constructor """

        it = iter(test_inputs.split("\n")) if test_inputs else None

        def uinput():
            return next(it) if it else sys.stdin.readline().rstrip()

        # Reading single elements
        [self.n] = list(map(int, uinput().split()))

        # Reading a single line of multiple elements
        self.nums = []
        for i in range(self.n*2-1):
            self.nums.append(list(map(int, uinput().split())))

        # Translating into pairs dict
        self.pairs = []
        for i in range(len(self.nums)):
            for j in range(len(self.nums[i])):
                self.pairs.append((self.nums[i][j], i+1, j))

        self.spairs = reversed(sorted(self.pairs))

    def calculate(self):
        """ Main calcualtion function of the class """

        result = [0] * (self.n * 2)

        paired = set()

        for p in self.spairs:
            if p[1] not in paired and p[2] not in paired:
                result[p[1]] = p[2] + 1
                result[p[2]] = p[1] + 1
                paired.add(p[1])
                paired.add(p[2])

        return str(" ".join(map(str, result)))

###############################################################################
# Unit Tests
###############################################################################


class unitTests(unittest.TestCase):

    def test_single_test(self):
        """ Member class testing """

        # Constructor test
        test = "2\n6\n1 2\n3 4 5"
        d = Member(test)
        self.assertEqual(d.n, 2)
        self.assertEqual(d.nums[0], [6])
        self.assertEqual(d.nums[1], [1, 2])

        # Sample test
        self.assertEqual(Member(test).calculate(), "2 1 4 3")

        # Sample test
        test = (
            "3\n487060\n3831 161856\n845957 794650 976977\n" +
            "83847 50566 691206 498447\n" +
            "698377 156232 59015 382455 626960")
        self.assertEqual(Member(test).calculate(), "6 5 4 3 2 1")

        # Sample test
        test = ""
        # self.assertEqual(Member(test).calculate(), "0")

        # My tests
        test = ""
        # self.assertEqual(Member(test).calculate(), "0")

        # Time limit test
        # self.time_limit_test(5000)

    def time_limit_test(self, nmax):
        """ Timelimit testing """
        import random
        import timeit

        # Random inputs
        test = str(nmax) + " " + str(nmax) + "\n"
        numnums = [str(i) + " " + str(i+1) for i in range(nmax)]
        test += "\n".join(numnums) + "\n"
        nums = [random.randint(1, 10000) for i in range(nmax)]
        test += " ".join(map(str, nums)) + "\n"

        # Run the test
        start = timeit.default_timer()
        d = Member(test)
        calc = timeit.default_timer()
        d.calculate()
        stop = timeit.default_timer()
        print(("\nTimelimit Test: " +
              "{0:.3f}s (init {1:.3f}s calc {2:.3f}s)".
              format(stop-start, calc-start, stop-calc)))

def __starting_point():

    # Avoiding recursion limitaions
    sys.setrecursionlimit(100000)

    if sys.argv[-1] == "-ut":
        unittest.main(argv=[" "])

    # Print the result string
    sys.stdout.write(Member().calculate())

__starting_point()

import operator

n = int(input())
dict = {}
for i in range(2, 2 * n + 1):
    L = list(map(int, input().split()))
    for j in range(len(L)):
        dict[L[j]] = (i, j + 1)

sorted_dict = sorted(dict.items(), key = operator.itemgetter(0), reverse = True)
#print(sorted_dict)
ans = [0] * 2 * n

for i in sorted_dict:
    if ans[i[1][0] - 1] == 0 and ans[i[1][1] - 1] == 0:
        ans[i[1][0] - 1] = i[1][1]
        ans[i[1][1] - 1] = i[1][0]
        
print(' '.join(map(str, ans)))

n = int(input())
table = []
for i in range(2 * n - 1):
    li = list(map(int, input().split()))
    for j in range(i+1):
        table.append([li[j], i+2, j+1])

table.sort(key=lambda x:(x[0]), reverse=True)
res = [0 for _ in range(2 * n)]
entry = 0
idx = 0
while entry != n:
    t = table[idx]
    t1, t2 = t[1] - 1, t[2] - 1
    if res[t1] == 0 and res[t2] == 0:
        res[t1] = t2 + 1
        res[t2] = t1 + 1
        entry += 1
    idx += 1
print(" ".join(map(str, res)))


n=int(input())
l=[]
for i in range(2,2*n+1):
  if i==2: s=[0,int(input())]
  else: s=[0]+list(map(int,input().split()))
  for j in range(1,i):
    l+=[(s[j],i,j)]
l=sorted(l)
s=set()
k=[0]*(2*n+1)
for x in l[::-1]:
  if x[1] in s or x[2] in s: continue
  s|={x[1],x[2]}
  k[x[1]]=x[2]
  k[x[2]]=x[1]
print(' '.join(map(str,k[1:])))


def aaa():
    n = int(input())
    n*=2
    a = [[0,0,0]]*(n*(n+1)//2)
    b = [[]]*n
    used = [-1]*(n+1)
    for i in range(1,n):
        b[i] = list(map(int, input().split()))
    k = 0
    for i in range(1, n):
        for j in range(i):
            a[k] = [b[i][j],i,j]
            k+=1
    a.sort(reverse=1)
    k = n-1
    for i in range(k*(k+1)//2):
        if used[a[i][1]]==-1 and used[a[i][2]]==-1:
            used[a[i][1]] = a[i][2]
            used[a[i][2]] = a[i][1]
        #print(*used)
    for i in range(n):
        print(used[i]+1, end = ' ')
aaa()

import heapq

n = int(input()) * 2
ans = [-1] * (n + 1)

h = []

for i in range(2, n + 1):
    j = 1
    for e in input().split():
        x = int(e)
        heapq.heappush(h, [-x, i, j])
        j += 1

i = 1
while True:
    cur = heapq.heappop(h)
    if ans[cur[1]] == -1 and ans[cur[2]] == -1:
        ans[cur[1]] = cur[2]
        ans[cur[2]] = cur[1]
        
    while ans[i] != -1 and i < n:
        i += 1
    if i == n:
        break

print(*ans[1:])

n = int(input())
N = 2 * n
ans = [None] * N
a = [list(map(int, input().split())) for i in range(N - 1)]

used = [False] * N
inf = 10 ** 9
for i in range(n):
    Max = -inf
    for i in range(N - 1):
        if not used[i + 1]:
            for j in range(i + 1):
                if not used[j] and a[i][j] > Max:
                    Max = a[i][j]
                    x, y = i + 1, j
    used[x] = True
    used[y] = True
    ans[x] = y + 1
    ans[y] = x + 1

print(' '.join(map(str, ans)))


def main():
    mode="filee"
    if mode=="file":f=open("test.txt","r")

    if mode=="file":n=int(f.readline())
    else:n=int(input())
    w=[]
    for i in range(2,2*n+1):
        if mode=="file":g=[int(x) for x in f.readline().split()]
        else:g=[int(x) for x in input().split()]
        for j in range(1,i):
            w.append([g[j-1],[i,j]])
    w.sort()
    free=2*n
    fr=[-1]*(free+1)
    w.reverse()
    for e,k in w:
        if fr[k[0]]==-1 and fr[k[1]]==-1:
            fr[k[0]]=k[1]
            fr[k[1]]=k[0]
            free-=1
            if free==0:
                break
    for i in fr[1:]:
        print(i,end=' ')
            

    if mode=="file":f.close()


def __starting_point():
    main()

__starting_point()

from collections import defaultdict
n=int(input())
d=defaultdict()
t=0
b=[]
c=[]
aa=[0]*((2*n)+1)
while t<2*n-1:
   # print(t)
    a=[int(x) for x in input().split()]
    for i in range(len(a)):
        d[a[i]]=[t+2,i+1]
    t=t+1
l=sorted(d.items())
#print(l)
i=len(l)-1
k=0
while i>=0:
    
    if aa[l[i][1][0]]==0 and aa[l[i][1][1]]==0:
        aa[l[i][1][0]]=l[i][1][1]
        aa[l[i][1][1]]=l[i][1][0]
        k=k+2
        if k==(2*n):
            break
        #print(aa)
    i=i-1    
for i in range(1,(2*n)+1):
    print(aa[i],end=" ")
  


from heapq import heapify
from heapq import heappop


def cmp(a, b):
    return a[0] > a[1]


n = int(input())
arr = []
for i in range(n * 2):
    arr.append([None] * (n * 2))
elems = []
for i in range(1, (n * 2)):
    lst = list(map(int, input().split()))
    for j in range(len(lst)):
        elems.append([-lst[j], i, j])
heapify(elems)
players = [True] * (n * 2)
rez = [None] * (n * 2)
cnt = 0
while elems and cnt != n:
    w, a, b = heappop(elems)
    if players[a] and players[b]:
        players[a] = False
        players[b] = False
        cnt += 1
        rez[a] = b
        rez[b] = a
for i in range(n * 2):
    print(rez[i] + 1, end=' ')

n = int(input())
ans = [0] * (n * 2 + 1)
used = [False] * (n * 2 + 1)
arr = []
for i in range(2, n * 2+1):
    qwe = [0] + [int(x) for x in input().split()]
    for j in range(1, i):
        arr.append((qwe[j], i, j))     

arr.sort(reverse=True)
for x in arr:
    if not(used[x[1]]) and not(used[x[2]]):
        used[x[1]] = used[x[2]] = True
        ans[x[1]] = x[2]
        ans[x[2]] = x[1]

print(*ans[1:])

import sys; sys.setrecursionlimit(1000000); import math
def solve():
    n, = rv()
    l = list()
    already = [-1] * (2 * n)
    for i in range(2 * n - 1):
        temp, = rl(1)
        for j, val in enumerate(temp):
            l.append((val, i + 1, j))
    l.sort(key = lambda x : -x[0])
    for tup in l:
        f, s = tup[1], tup[2]
        if already[f] == -1  and already[s] == -1:
            already[f] = s
            already[s] = f
    print(' '.join(map(str, [val + 1 for val in already])))


def rv(): return list(map(int, input().split()))
def rl(n): return [list(map(int, input().split())) for _ in range(n)]
if sys.hexversion == 50594544 : sys.stdin = open("test.txt")
solve()



#!/usr/bin/env python3
import sys

N = int(input())

score_pairings = []
partner_of = {}
people_with_partners = set()

for k in range(2*N - 1):
  i = k + 2
  line = list(map(int, input().split()))
  for j in range(1, i):
    score_pairings += [(line[j-1], (i, j))]

score_pairings = sorted(score_pairings)[::-1]

for score, (i, j) in score_pairings:
  if i in people_with_partners or j in people_with_partners:
    continue
  partner_of[i] = j
  partner_of[j] = i
  people_with_partners.add(i)
  people_with_partners.add(j)

print(' '.join(str(partner_of[i]) for i in partner_of))

n = int(input())
a = []; b = [0]*(2*n+1); c = [0]*(2*n+1);
z = dict()
for i in range(2*n-1):
    k = list(map(int, input().split()));
    for j in range(len(k)):
        z[k[j]] = (i+2, j+1)
    a += k
a.sort(reverse = True)
for d in range(len(a)):
    i, j = z[a[d]]
    if not c[i] and not c[j]:
        b[i] = j
        b[j] = i
        c[i] = c[j] = True
for i in range(1, 2*n+1):
    print(b[i], end=' ')


n = int(input())
a = []
team = [None] * (n + n)
for i in range(1, n + n):
    for j, v in enumerate(map(int, input().split())):
        a.append((v, i, j))
a.sort(reverse=True)

for _, i, j in a:
    if team[i] is None and team[j] is None:
        team[i] = j + 1
        team[j] = i + 1

print(' '.join(str(i) for i in team))


import sys

#sys.stdin = open("input.txt")
#sys.stdout = open("output.txt", "w")

n = int(input())
stud = []
for i in range(1, 2*n):
	lst = [int(x) for x in input().split()]
	for j in range(len(lst)):
		stud += [(lst[j], j, i)]

stud.sort(reverse = True)
ans = [-1 for x in range(2 * n)]

for item in stud:
	first = item[1]
	second = item[2]
	if ans[first] == ans[second] == -1:
		ans[first] = second
		ans[second] = first

for x in ans:
	print(x + 1, end = ' ')
print()




def main():
    n = int(input())
    N = 2 * n
    ans = [None] * N
    a = [list(map(int, input().split())) for i in range(N - 1)]

    used = [False] * N
    for i in range(n):
        Max = -(10 ** 9)
        for i in range(N - 1):
            if used[i + 1]:
                continue
            for j in range(i + 1):
                if not used[j] and a[i][j] > Max:
                    Max = a[i][j]
                    x, y = i + 1, j
        used[x] = used[y] = True
        ans[x], ans[y] = y + 1, x + 1

    print(' '.join(map(str, ans)))
main()

def getKey(item):
        return item[2]

n = int(input())

li = []

for _ in range(n*2-1):
    li.append([int(x) for x in input().split()])

ans = [0]*(2*n+5)

dict = []

for i in range(2*n-2,-1,-1):
    for j in range(0,i+1):
        dict.append([i+2,j+1,li[i][j]])

dict = sorted(dict, key=getKey, reverse=True)

#print(dict)

for i in dict:
    if ans[i[0]] == 0 and ans[i[1]] == 0:
        ans[i[0]] = i[1]
        ans[i[1]] = i[0]

print(' '.join(map(str,ans[1:2*n+1])))