Restore the Celestial Password

You are given n multisets S1, S2, …, Sn corresponding to a secret password. The celestial password is a permutation P of the numbers from $1$ to $n$. For each integer $l$ ($1 \le l \le n$), the multiset Sl is defined as the collection of the minimum values of every contiguous subarray of P of length $l$. In other words, if P = $[p_1, p_2, \ldots, p_n]$, then for every contiguous interval of length $l$, the minimum value is computed and all these values (with repetition) form Sl.

You are guaranteed that the given multisets come from at least one valid permutation. Your task is to restore one possible password P which, if processed, would yield the provided multisets.

Note: All formulas (e.g. $1\sim n$, $S_l$) are written in LaTeX format.

inputFormat

The input begins with a single integer n ($1 \le n \le 10^5$), representing the length of the password. The following n lines describe the multisets:

• The first line contains n space‐separated integers, which form S1 (this multiset is exactly the set of numbers in the permutation).
• The second line contains n-1 space‐separated integers, which form S2.
• …
• The n-th line contains a single integer, which is Sn.

It is guaranteed that these multisets are consistent with at least one valid permutation.

outputFormat

Output a single line containing n space‐separated integers – the recovered permutation (the celestial password). If there are multiple answers, output any one of them.

sample

3
1 2 3
1 2
1

1 2 3