P12426 [BalticOI 2025] BOI acronym

众所周知，BOI 是 Baltic Olympiad in Informatics（波罗的海信息学奥林匹克竞赛）名称的缩写。 主办方认为缩写 BOI 太容易发音（毕竟它在英语中是一个单音节词）。因此，他们提出了一个新的缩写。为了与其他区域性奥林匹克竞赛（如 CEOI）轻松区分，新缩写仍然仅由字符 "B"、"O" 和 "I" 组成。此外，"B" 必须是缩写中严格最常见的字符。也就是说，"B" 的出现次数严格多于 "O"，同时也严格多于 "I"。 例如，缩写 "OBOIIBBB" 和 "B" 是有效的，但 "IBIIBB"、"BOI"、"O" 和 "BCB" 不是。 为了让事情更有趣，主办方没有直接公布完整的缩写，而是只提供了一些提示。具体来说，对于新缩写的每个连续子串，他们给出了该子串中最常见字符的出现次数。注意，这个字符不一定是 "B"，而且最常见字符也不一定是唯一的。令人惊讶的是，可以证明这些信息实际上足以还原所有 "B" 的出现位置。你能找到它们吗？

第一行包含一个整数 $n$（$1 \leq n \leq 2000$），表示新缩写的长度。 接下来的 $n$ 行描述了提示。第 $i$ 行包含 $n-i+1$ 个整数 $M_{i,i}, M_{i,i+1}, \ldots, M_{i,n}$（$1 \leq M_{\ell,r} \leq n$），其中 $M_{\ell,r}$ 表示从缩写的第 $\ell$ 个位置开始到第 $r$ 个位置结束的子串中最常见字符的出现次数。位置编号从 1 到 $n$。 你可以假设至少存在一个有效的缩写与给定的提示一致。

输出一行，包含所有 "B" 出现的位置，按递增顺序排列，用单个空格分隔。每个位置必须是 1 到 $n$ 范围内的整数。

### 评分 | 子任务 | 限制条件 | 分值 | | :---: | :---: | :---: | | 1 | $n \leq 10$ | 11 | | 2 | 所求缩写仅包含字符 "B" 和 "O"。 | 12 | | 3 | 所求缩写中没有两个连续的相同字符。 | 10 | | 4 | $n \leq 40$ | 11 | | 5 | $n \leq 500$ | 19 | | 6 | 无额外限制。 | 37 | 翻译由 DeepSeek V3 完成