众所周知，$BOI$ 是波罗的海信息学奥林匹克竞赛（Baltic Olympiad in Informatics）的缩写。 组织者认为 $BOI$ 这个缩写太容易发音了（毕竟它在英语中只构成一个音节）。因此，他们想出了一个新的缩写。为了将其与其它区域性奥林匹克竞赛（如 $CEOI$）轻松区分开来，新缩写仍然仅由字符“B”、“O”和“I”组成。此外，“B”是该缩写中严格出现次数最多的字符。也就是说，“B”出现的次数严格多于“O”，且“B”出现的次数也严格多于“I”。 例如，缩写“OBOIIBB”和“B”是合法的，但“IBIIBB”、“BOI”、“O”和“BCB”不是。 为了增加趣味性，他们没有公布完整的缩写，而只提供了一些提示。具体来说，对于新缩写的每一个连续子串，他们给出了该子串中出现次数最多的字符的出现次数。注意，这个字符不一定是“B”，且出现次数最多的字符也不一定是唯一的。令人惊讶的是，可以证明这些信息足以恢复所有“B”出现的位置。你能找到它们吗？

输入格式

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

输出格式

输出一行，包含所有“B”出现的位置，按升序排列，并用空格分隔。每个位置必须是 $1$ 到 $n$ 之间的整数。

样例

样例输入 1

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

样例输出 1

1 3 4

子任务