boi (BOI contest)
Time limit: 1 seconds | Memory limit: 256 MB | Task type: batch
Algorithms: dynamic programming, string, union-find

# Task: BOI Acronym
![BOI Logo](_page_0_Picture_1.jpeg)

**BOI 2025, Day 1. Available memory: 256 MB.** *2025.04.26*

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?

## Input

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<sub>i,i</sub>, M<sub>i,i+1</sub>, ..., M<sub>i,n</sub>* (1 ≤ *M<sub>ℓ,r</sub>* ≤ *n*), where *M<sub>ℓ,r</sub>* denotes the number of occurrences of the most common character in the substring that starts at the *ℓ*-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

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*.

## Example

**For the input data:**

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

**the correct result is:**

```
1 3 4
```

## Scoring

| Subtask | Constraints                                                | Points |
| :-------: | :--------------------------------------------------------- | :----: |
|     1     | *n* ≤ 10                                                 |   11   |
|     2     | The sought acronym contains only characters "B" and "O".   |   12   |
|     3     | The sought acronym has no two consecutive equal characters. |   10   |
|     4     | *n* ≤ 40                                                 |   11   |
|     5     | *n* ≤ 500                                                |   19   |
|     6     | No additional constraints.                                 |   37   |

Starter code:

Grader code:

Setup script:

Evaluation script: