Problem G: Eccentrics

I am sure you are aware of the EuroMillions lottery, the lottery that creates eccentric people. And perhaps you know how the draws are made. There’s this huge transparent sphere with coloured balls inside, one ball for each number in the lottery. A strong stream of air is violently blown inside the sphere and the balls are made to fly like crazy, in all directions, until they are well shuffled. Then, the wind inside the sphere stops and one ball comes out, thus yielding a number. Afterwards, the wind starts again and the procedure repeats until the required number of balls are extracted.

This is all fine, but recently the Society for the Protection of Lottery Balls launched a protest movement, claiming that the balls are subject to excessive stress when they have to tumble inside the sphere, pushed by the irrational stream of air. They suggest an alternative, more gentle procedure.

Instead of a windy sphere, a static inverted tetrahedron is used. The base of the tetrahedron, which is facing upwards, is open. The balls are to be dropped simultaneously from a height, in such a way that they fall inside the tetrahedron. This, the Society claims, ensures enough randomness, and it seems the balls actually enjoy free falling. Then, the tip of the tetrahedron (which is pointing downwards) opens, allowing for just one ball to come out. That’s the ball that was at the bottom tip of the tetrahedron, of course. As the first ball comes out, one of the balls in the second layer moves down, filling the empty space, so to speak. And a ball from the third layer moves down, to fill the empty space left by the ball from the second layer that moved down. And so on, up to the top layer of balls.

The following figure illustrates the original configuration of the inside of the tetrahedron after 120 coloured balls have been randomly dropped into it, filling exactly eight layers:

Your task is to prove by computer that this system is biased. In fact, physicists have pointed out that, all balls being made with the same material, heavier balls glide down first. More precisely, when an empty space is created because a ball has moved down, of all the balls than can fill that empty space (there can be zero, one, two or three such balls, on the layer above the layer of the empty space that was just created), gravity will choose the heaviest, provided there is at least one.

No ties will ever occur, because it is impossible to produce balls with exactly the same weight.

Task

Write a program that, given a description of the balls inside the tetrahedron, computes the sequence of balls falling out from the bottom tip of the tetrahedron, once the tip opens.

Input

The first line of the input contains one positive integer, N, representing the number of layers of balls inside the tetrahedron. All layers are full.

Each layer S, for S ∈ {1, 2, …, N}, is represented by S consecutive input lines of positive integers, in a triangular pattern: the first line has one number, the second line, two numbers, etc., and the S-th line, S numbers. Each number represents the weight of a ball and there are no duplicate numbers. Hence, the weights uniquely represent the balls.

Each triangle of numbers, in the input, represents graphically the arrangement of balls in the respective layer.

Constraints

Output

The output shall contain one line for each ball, in the order they fall out from the bottom of the tetrahedron.

Sample Input

3
9
1
8 7
5
2 3
4 10 11 

Sample Output

9
8
10
7
11
4
3
2
1
5

Sample Explanation

There are three layers. The first ball to fall out is the ball at the bottom, 9. All three balls at the second layer could, in principle, move down to fill the space left empty when ball 9 fell out. The heaviest of the three is ball 8. Hence, this one moves down, to the place which previously was occupied by ball 9. The balls on the third layer that could move down to the place vacated when ball 8 descended are 2, 4 and 10. The heaviest is 10. This is the one that descends. The third layer is the top layer, so there are no balls to fill the place vacated by ball 10.

The bottom ball is now 8. It falls out. On the second layer we have balls 1, 7 and 10. Hence 10, being the heaviest, descends. The balls on the third layer that could descend to fill the place vacated by ball 10 are balls 2 and 4. The heaviest is 4. This is the ball that descends, to fill the place previously occupied by ball 10.

Next ball to fall out is 10. On the second layer, we now have 1, 4 and 7. The heaviest is 7. It comes down. On the third layer, the balls that could now descend are 3 and 11. Hence, 11 descends.

And so on. The full story is depicted in the following figure, in which we are looking at the tetrahedron from below: