33854번 - BOI acronym 서브태스크다국어

문제

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 “OBOIIBB” 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ドル ≤ n ≤ 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}, \dots , M_{i,n}$ (1ドル ≤ M_{l,r} ≤ n$), where $M_{l,r}$ denotes the number of occurrences of the most common character in the substring that starts at the $l$-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$.

제한

서브태스크

힌트