Description

This problem is collecting an SPJ. However, if you submit the correct solution, i.e., output the lexicographically smallest solution, you can still get AC.

Xiao Bin likes playing jigsaw puzzles.

Xiao Bin got a one-dimensional jigsaw puzzle game consisting of $n$ pieces. He soon realized that each piece belongs to one of the following types:

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

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

This is too easy for Xiao Bin, so he decided to write a unique positive integer on each piece. Now he wants to find the lexicographically smallest arrangement.

Note: Pieces cannot be rotated.

Input Format

The input has $n + 1$ lines.

The first line contains a positive integer $n$.

Each of the next $n$ lines contains two integers $x_i$ and $a_i$. Here, $x_i$ denotes the type of the piece, and $a_i$ is the number Fabian wrote on it. The input guarantees that all $a_i$ are distinct.

Output Format

Output one line.

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

5
1 5
2 7
2 3
8 4
6 1

1 3 7 5 4

3
5 1
7 2
4 3

1 3 2

5
2 5
2 7
2 3
8 4
6 1

-1

Hint

Sample #1 Explanation

There are only $2$ solutions, as shown below:

You can see that the second solution is lexicographically smaller, so the output is 1 3 7 5 4.

Constraints

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

If you do not output the lexicographically smallest solution and only construct any valid solution, you can get $40\%$ of the score.

Notes

The score of this problem follows the original COCI setting, with a full score of $70$.

Translated from COCI2019-2020 CONTEST #2 T2 Slagalica.

Translated by ChatGPT 5