题目描述

你肯定知道，BOI 是波罗的海信息学奥林匹克竞赛（Baltic Olympiad in Informatics）的缩写。

不过，主办方觉得 BOI 这个缩写念起来太简单了（毕竟在英语里它只有一个音节）。所以，他们决定设计一个新的缩写。为了让它与 CEOI 等其他区域性奥林匹克竞赛的缩写区分开来，新缩写依然只由字符 B、O 和 I 组成。而且，B 必须是新缩写中最常见的字符，也就是说，B 的出现次数必须严格多于 O 和 I 的出现次数。

例如，OBOIIBB 和 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$ 范围内的整数。

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

数据范围与提示

详细子任务附加限制及分值如下表所示。