小 Fabian 得到了一个由 $N$ 块碎片组成的一维拼图。他很快发现，每块碎片都属于以下类型之一：

此外，已知在这 $N$ 块碎片中，恰好有一块是 5 型或 6 型（左边界），且恰好有一块是 7 型或 8 型（右边界）。

Fabian 希望将所有碎片排成一排，使得第一块（最左边）碎片是 5 型或 6 型，最后一块（最右边）碎片是 7 型或 8 型。两块碎片可以相邻放置，当且仅当它们相邻的边界形状不同，即一个是凸起（也称为凸头），另一个是凹槽（也称为凹口）。

仅仅拼好拼图对 Fabian 来说太简单了，因此他决定在每块碎片上写一个唯一的正整数。现在，他想找到该拼图的字典序最小的解。如果两个解 $A$ 和 $B$ 在从左往右第一个不同的位置 $i$ 上，解 $A$ 中第 $i$ 块拼图上的数字小于解 $B$ 中第 $i$ 块拼图上的数字，则认为解 $A$ 的字典序比解 $B$ 小。

注意：碎片不能旋转。

输入格式

第一行包含一个整数 $N$（$2 \le N \le 10^5$），表示碎片数量。

接下来的 $N$ 行，每行包含两个整数 $X_i$（$1 \le X_i \le 8$）和 $A_i$（$1 \le A_i \le 10^9$），分别表示第 $i$ 块碎片的类型以及 Fabian 在上面写的数字。所有数字 $A_i$ 互不相同。

输出格式

如果 Fabian 无法拼好拼图，应在单行中输出 -1。

否则，应输出拼图字典序最小解中各碎片上的数字，数字之间用空格分隔。

子任务

• 在价值 5 分的测试数据中，满足 $N \le 4$。
• 在额外价值 5 分的测试数据中，满足 $N \le 10$。
• 在额外价值 10 分的测试数据中，输入中不会出现 2 型和 3 型碎片。
• 在额外价值 20 分的测试数据中，最多只有一块 1 型或 4 型碎片。

对于某个存在解的测试点，如果你输出了一组正确的拼图解，但该解不是字典序最小的，你将获得该测试点 40% 的分数。

样例

输入样例 1

5
1 5
2 7
2 3
8 4
6 1

输出样例 1

1 3 7 5 4

输入样例 2

3
5 1
7 2
4 3

输出样例 2

1 3 2

输入样例 3

5
2 5
2 7
2 3
8 4
6 1

输出样例 3

-1

说明

样例 1 解释

该拼图仅有两种可能的解：

我们可以看到，图中所示的第二个解在第二块碎片上写有较小的数字。因此，该解是字典序最小的解。