Background

By exploring the ancient archives, you successfully built the Astral Detector. You need to use it to discover hidden astral technology.

Problem Description

To find the astral technology, you first need to obtain a string of astral codes—it is a permutation of $1 \sim n$.

The Astral Detector can, for a given length $l$, return the minimum value of an interval of length $l$ in the code.

Unfortunately, the minimum values of all intervals of length $l$ are mixed together. What you get is only $n$ multisets $S_1, \ldots , S_n$:

• $S_i$ denotes the multiset formed by the minimum values of all intervals of length $i$.

You need to reconstruct one possible astral code from these $S_i$. It is guaranteed that at least one correct astral code exists.

Input Format

The first line contains an integer $n$, representing the length of the astral code.

The next $n$ lines follow. The $i$-th line contains $n - i + 1$ integers (there are $n - i + 1$ intervals of length $i$), representing each element in the multiset $S_i$. Note that the order of the elements is arbitrary, and is not necessarily the left-to-right order of the intervals.

Output Format

Output one line with $n$ integers $p_1, p_2, \ldots , p_n$, representing the astral code you reconstructed.

If there are multiple feasible solutions, you may output any one of them.

4
4 3 2 1
1 2 1
1 1
1

3 1 2 4

Hint

[Sample 1 Explanation]

The astral code in the sample output is: $p = [3, 1, 2, 4]$.

The multiset of minimum values of intervals of length $1$: $S_1 = \{ 3, 1, 2, 4 \} = \{ 4, 3, 2, 1 \}$.

The multiset of minimum values of intervals of length $2$: $S_2 = \{ \min(3, 1), \min(1, 2), \min(2, 4) \} = \{ 1, 1, 2 \} = \{ 1, 2, 1 \}$.

The multiset of minimum values of intervals of length $3$: $S_3 = \{ \min(3, 1, 2), \min(1, 2, 4) \} = \{ 1, 1 \}$.

The multiset of minimum values of intervals of length $4$: $S_4 = \{ \min(3, 1, 2, 4) \} = \{ 1 \}$.

Each $S_i$ corresponds to the input.

Other feasible answers are also accepted, such as $p = [4, 2, 1, 3]$.

[Constraints]

This problem uses bundled testdata.

For $100\%$ of the data: $2 \le n \le 800$.

Translated by ChatGPT 5