Description

众所周知，BOI 是 Baltic Olympiad in Informatics（波罗的海信息学奥林匹克竞赛）名称的缩写。

主办方认为缩写 BOI 太容易发音（毕竟它在英语中是一个单音节词）。因此，他们提出了一个新的缩写。为了与其他区域性奥林匹克竞赛（如 CEOI）轻松区分，新缩写仍然仅由字符 "B"、"O" 和 "I" 组成。此外，"B" 必须是缩写中严格最常见的字符。也就是说，"B" 的出现次数严格多于 "O"，同时也严格多于 "I"。

例如，缩写 "OBOIIBBB" 和 "B" 是有效的，但 "IBIIBB"、"BOI"、"O" 和 "BCB" 不是。

为了让事情更有趣，主办方没有直接公布完整的缩写，而是只提供了一些提示。具体来说，对于新缩写的每个连续子串，他们给出了该子串中最常见字符的出现次数。注意，这个字符不一定是 "B"，而且最常见字符也不一定是唯一的。令人惊讶的是，可以证明这些信息实际上足以还原所有 "B" 的出现位置。你能找到它们吗？

Input Format

第一行包含一个整数 $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$。

你可以假设至少存在一个有效的缩写与给定的提示一致。

Output Format

输出一行，包含所有 "B" 出现的位置，按递增顺序排列，用单个空格分隔。每个位置必须是 1 到 $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

Hint

评分

翻译由 DeepSeek V3 完成