Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

brute force

implementation

sortings

*1300

No tag edit access

The problem statement has recently been changed. View the changes.

×
B. Finding Team Member

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThere is a programing contest named SnakeUp, 2*n* 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 2*n* 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*_{i1}, *a*_{i2}, ... , *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 2*n* 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.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/02/2023 23:52:33 (k3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|