Little Fabian got a o\(ne-di\)mensional 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.

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% of the points intended for that test case.

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@@RISE_MATH_BLOCK_0@@i \le 8\)) and \(A@@RISE_MATH_BLOCK_1@@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.

If Fabian cannot solve the jigsaw puzzle, you should outp\(ut - 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.

생성자가 기록되지 않았습니다.

출처 COCI 2019/2020 Contest 2