Lexicographically Small Puzzle Arrangement

You are given a one‐dimensional puzzle game consisting of n pieces. Each piece belongs to one of eight types and has a unique positive integer inscribed on it. The pieces have fixed border shapes on their left and right sides as follows (expressed in LaTeX):

• For interior pieces (types 1–4):
  • Type 1 and Type 3: left border = $1$, right border = $-1$.
  • Type 2 and Type 4: left border = $-1$, right border = $1$.
• For border pieces:
  • Left border pieces (types 5 and 6): left border = $0$ (flat), and
    • Type 5: right border = $1$.
    • Type 6: right border = $-1$.
  • Right border pieces (types 7 and 8): right border = $0$ (flat), and
    • Type 7: left border = $1$.
    • Type 8: left border = $-1$.

It is guaranteed that among the n pieces there is exactly one left border piece (i.e. a piece of type $5$ or $6$) and exactly one right border piece (i.e. a piece of type $7$ or $8$).

Your task is to arrange all the pieces in a line so that:

1. The first piece is a left border piece (type $5$ or $6$) and the last piece is a right border piece (type $7$ or $8$).
2. For any two adjacent pieces, let the right border of the left piece be r and the left border of the right piece be ℓ. These two pieces can be placed adjacently if and only if $r\cdot\ell = -1$, i.e. one of them is $1$ and the other is $-1$.

Among all valid arrangements, output the lexicographically smallest sequence based on the inscribed integers. Here, lexicographical order means that given two sequences, the one with the smaller integer at the first differing position is considered smaller.

If no valid arrangement exists, output -1.

Note: Pieces cannot be rotated.

inputFormat

The first line contains an integer n --- the number of puzzle pieces. Each of the next n lines contains two integers t and a, where t (1 ≤ t ≤ 8) denotes the type of the puzzle piece and a is its unique positive integer inscribed on it.

outputFormat

If a valid arrangement exists, output the inscribed numbers of the pieces in order (separated by a space) that forms the lexicographically smallest sequence. Otherwise, output -1.

sample

3
6 2
1 4
7 3

2 4 3