In The man who loved only numbers, Paul Hoffman gives a very absorving memoir of the brilliant number theorist Paul Erdös through the recollections of many of his collaborators, specially the mathematician Ronald L. Graham. One area were Erdös and Graham got very much involved was the Ramsey theory.

Here we take a simple example of Ramsey theory to pose a challenge to you. Consider the first 101 integers and arrange them in any order you like. No matter the arrangement, you will always be able to find 11 integers that form an increasing or a decreasing sequence. As said by Graham: "You don't have to pick the integers consecutively. You can jump. You might pick the first one, then the thirty-eighth one - but they all have to be going up or going down". This would not necessarily be true if you only had the first 100 integers, as it is possible to give a sequence of those 100 integers such that there is no increasing or decreasing sequence of 11 integers.

Ramsey theory generalizes this result: "to guarantee either a rising or falling sequence of length n+1, you need n²+1 numbers; with n² numbers, you may not get it".

Discovering such a sequence is challenging, but we invite you for a slightly bigger challenge, that is, to determine the longest rising (increasing) or falling (decreasing) sequence for a given n. It follows from the above result that the sequence has at least n+1 numbers.

Problem

Your task is to write a program to compute the longest rising or falling sequence of integers, given an arrangement of the first n²+1 integers.

You should always output the longest rising or falling sequence that appears first in the given sequence of numbers. If this rule is not enough to take a decision, then you should output the rising sequence.

Input

The input is composed by the integer value of n (0 < n ≤ 100) in the first line, followed by n²+1 different integers, each in a separate line, comprehended between 1 and n²+1.

Output

Your output should be the first longest rising or falling sequence of integers, from the arrangement given as input, considering the rules above. Each number in the sequence should be printed in a separate line.

Sample Input

3
5
6
3
2
9
1
8
4
7
10

5
6
9
10