题目描述

As you certainly know, BOI is an acronym for the name of the Baltic Olympiad in Informatics.

The organisers find the acronym BOI too easy to pronounce (it forms a single syllable in the English language, after all). Therefore they came up with a new acronym. In order to easily distinguish it from the other regional Olympiads (like CEOI), the new acronym still consists only of characters "B", "O" and "I". Additionally, "B" is strictly the most common character in the acronym. That is, there are strictly more occurrences of "B" than "O", and there are also strictly more occurrences of "B" than "I".

For example, acronyms "OBOIIBBB" and "B" are valid, but "IBIIBB", "BOI", "O" and "BCB" are not.

To make things more exciting, instead of publishing it in full they have only provided some hints. Namely, for each consecutive substring of the new acronym, they gave you the number of occurrences of the most common character in this substring. Note that this character is not necessarily "B", and also the most common character is not necessarily unique. Surprisingly, it can be proven that this information is actually enough to recover all the occurrences of "B". Can you find them?

输入格式

The first line contains an integer $n$ ($1 \leq n \leq 2000$), denoting the length of the new acronym.

The following $n$ lines describe the hints. The $i$-th line contains $n-i+1$ integers $M_{i,i}, M_{i,i+1}, \ldots, M_{i,n}$ ($1 \leq M_{\ell,r} \leq n$), where $M_{\ell,r}$ denotes the number of occurrences of the most common character in the substring that starts at the $\ell$-th position and ends at the $r$-th position of the acronym. The positions are numbered from 1 to $n$.

You can assume that there exists at least one valid acronym that is consistent with the given hints.

输出格式

Output one line with the positions of all occurrences of "B", in the increasing order, separated by single spaces. Each position must be an integer in the range from 1 to $n$.

6
1 1 2 3 3 3
1 1 2 2 2
1 2 2 2
1 1 2
1 2
1

1 3 4

提示

Scoring