Little Fabian got a one-dimensional jigsaw puzzle that consists of $N$ pieces. He quickly realized that each piece belongs to one of the following types:

Additionally, it is known that among those $N$ pieces there is exactly one piece of either type $5$ or type $6$ (left border) and exactly one piece of either type $7$ or type $8$ (right border).

Fabian wishes to arrange all of the pieces into a single row such that the first (leftmost) piece is of type $5$ or $6$ and the last (rightmost) piece is of type $7$ or $8$. Two pieces can be placed next to each other if and only if their neighbouring borders are of different shapes, i.e., one has a bump (also called outie or tab) and the other has a hole (also called innie or blank).

Simply solving the puzzle would be too easy for Fabian so he decided to write a unique positive integer on each of the pieces. Now he is interested in finding the lexicographically smallest solution to the jigsaw puzzle. The solution $A$ is considered lexicographically smaller than solution $B$ if at the first position (from the left) $i$ where they differ it holds that the number written on $i$-th puzzle in $A$ is smaller than the number written on $i$-th puzzle in $B$.

Note: the pieces cannot be rotated.

Input

The first line contains an integer $N$ $(2\le N\le {10}^5)$ from the task description.

The next $N$ lines contain two integers $X_i$ $(1\le X_i\le 8)$ and $A_i$ $(1\le A_i\le {10}^9)$ which represent the type of the $i$-th piece and the number Fabian wrote on it. All numbers $A_i$ will be different.

Output

If Fabian cannot solve the jigsaw puzzle, you should output -1 in a single line.

Otherwise, you should output the numbers that are written on the pieces in the lexicographically smallest solution to the puzzle.

Scoring

In test cases worth a total of $5$ points it will hold $N\le 4$.
In test cases worth additional $5$ points it will hold $N\le 10$.
In test cases worth additional $10$ points pieces of types $2$ and $3$ will not appear in the input.
In test cases worth additional $20$ points there will be at most one piece of type $1$ or $4$.

If for some test case in which the solution to the puzzle exists, you output the correctly solved puzzle but your solution is not lexicographically smallest, you will get $40\mathrm{\%}$ of the points intended for that test case.

Sample Input 1

5
1 5
2 7
2 3
8 4
6 1

Sample Output 1

1 3 7 5 4

Explanation For Sample 1

There are only two possible solutions to the puzzle:

We can see that the second depicted solution has a smaller number written on the second piece. Therefore, that is the lexicographically smallest solution.

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