Problem Background

This problem is collecting Special Judge (SPJ). However, if you submit the correct solution, which outputs the lexicographically smallest solution, you can still receive an AC verdict.

Xiao Bin enjoys playing puzzles.

Problem Description

Xiao Bin received a one-dimensional puzzle game consisting of $n$ parts. He quickly realized that each piece belongs to one of the following types:

Additionally, among these $n$ pieces, exactly one piece is a type $5$ or type $6$ (left border) and one piece is a type $7$ or type $8$ (right border).

Xiao Bin wants to arrange all the pieces in a row such that the first (leftmost) piece is a type $5$ or type $6$, and the last (rightmost) piece is a type $7$ or type $8$. Two pieces can be placed adjacent to each other only if their adjacent borders have different shapes, i.e., one border has a concave and the other has a convex shape.

For Xiao Bin, this problem is too simple, so he decided to write a unique positive integer on each piece. Now, he wants to find the lexicographically smallest arrangement.

Note: The puzzle pieces cannot be rotated!

Input Format

The input consists of $n + 1$ lines.

The first line contains a positive integer $n$.

The next $n$ lines contain two integers each, $x_i$ and $a_i$, representing the type of piece $i$, the piece number $x_i$, and the number $a_i$ written on it by Xiao Bin. It is guaranteed that all $a_i$ are unique.

Output Format

The output consists of one line.

If Xiao Bin cannot solve the puzzle, output -1. Otherwise, output the lexicographically smallest arrangement of the numbers on the pieces.

Sample Input and Output

Sample Input #1

5
1 5
2 7
2 3
8 4
6 1

Sample Output #1

1 3 7 5 4

Sample Input #2

3
5 1
7 2
4 3

Sample Output #2

1 3 2

Sample Input #3

5
2 5
2 7
2 3
8 4
6 1

Sample Output #3

-1

Notes

Sample #1 Explanation

There are only two solutions, as follows:

It can be seen that the second solution has a smaller lexicographical order, so the output is 1 3 7 5 4.

Data Size and Constraints

For $100\%$ of the data, $2 \le n \le 10^5, 1 \le x_i \le 8, 1 \le a_i \le 10^9$.

Constructing a solution without the lexicographically smallest solution can earn $40\%$ of the points.

Note

This problem's score is set according to the original COCI contest, with a full score of $70$.

The problem is translated from COCI2019-2020 CONTEST #2 T2 Slagalica.

见题面 Input 部分

见题面 Output 部分