每四年，隆德的学生们都会聚在一起举办隆德嘉年华。在几天的时间里，公园里搭满了帐篷，各种庆祝活动在此举行。负责筹备这一切的人被称为嘉年华将军。

总共有 $N$ 届嘉年华，每一届都有一位不同的将军。将军们按时间顺序编号为 $0$ 到 $N - 1$。每一位将军 $i$ 都通过发布一份将军 $0, 1, \dots, i - 1$ 的排名（从最好到最差）来表达他们对前任们的评价。

下一届隆德嘉年华将于 2026 年举行。在此期间，所有历届嘉年华将军都聚集在一起拍摄合影。然而，如果将军 $i$ 和 $j$（其中 $i < j$）相邻，且 $i$ 严格处于 $j$ 的排名的后半部分，那将会很尴尬。

例如： 如果将军 4 给出的排名是 3 2 1 0，那么 4 可以站在 3 或 2 旁边，但不能站在 1 或 0 旁边。 如果将军 5 给出的排名是 4 3 2 1 0，那么 5 可以站在 4、3 或 2 旁边，但不能站在 1 或 0 旁边。注意，如果某位将军恰好位于另一位将军排名的正中间，这是可以接受的。

下图展示了样例 1。在这里，将军 5 站在将军 2 和 3 旁边，而将军 4 仅站在将军 2 旁边。

你需要根据将军们发布的排名，将将军 $0, 1, \dots, N - 1$ 排成一行，使得对于任意相邻的将军 $i$ 和 $j$（假设 $i < j$），$i$ 不会严格处于 $j$ 的排名的后半部分。

输入格式

第一行包含一个正整数 $N$，表示将军的数量。

接下来的 $N - 1$ 行包含排名信息。第一行包含将军 1 的排名，第二行包含将军 2 的排名，以此类推，直到将军 $N - 1$。将军 0 不包含在内，因为将军 0 没有前任需要排名。

将军 $i$ 的排名是一个包含 $i$ 个整数 $p_{i,0}, p_{i,1}, \dots, p_{i,i-1}$ 的列表，其中 $0$ 到 $i - 1$ 的每个整数恰好出现一次。具体来说，$p_{i,0}$ 是将军 $i$ 眼中最好的将军，$p_{i,i-1}$ 是最差的将军。

输出格式

输出一个整数列表，即 $0, 1, \dots, N - 1$ 的一个排列，使得对于每一对相邻的数字，其中一个都不会严格处于另一个排名的后半部分。

可以证明解总是存在的。如果存在多个解，你可以输出其中任意一个。

数据范围

• $2 \le N \le 1000$。
• 对于 $i = 0, 1, \dots, N - 1$，排名中的元素满足 $0 \le p_{i,0}, p_{i,1}, \dots, p_{i,i-1} \le i - 1$。

子任务

样例

输入 1

6
0
1 0
2 1 0
3 2 1 0
4 3 2 1 0

输出 1

4 2 5 3 1 0

输入 2

5
0
0 1
0 1 2
0 1 2 3

输出 2

2 0 4 1 3

输入 3

4
0
1 0
0 2 1

输出 3

3 0 1 2

说明

第一个样例符合子任务 1 的条件。在此样例中，将军 2 和 3 都不能站在将军 0 旁边，将军 4 和 5 都不能站在将军 0 和 1 旁边。样例输出如上图所示。

第二个样例符合子任务 2 的条件。在此样例中，将军 2 不能站在将军 1 旁边，将军 3 不能站在将军 2 旁边，将军 4 不能站在将军 3 和 2 旁边。

第三个样例符合子任务 3 的条件。在此样例中，唯一不能相邻的将军对是 $(1, 3)$ 和 $(0, 2)$。因此，如果排列为 3 0 1 2，则没有冲突。另一个可能的答案是 0 1 2 3。