18092번 - Slagalica 다국어

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.

The first line contains an integer N (2 ≤ N ≤ 10⁵) from the task description.

The next N lines contain two integers X_i (1 ≤ X_i ≤ 8) and A_i (1 ≤ A_i ≤ 10⁹) 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 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.

Clarification of the first example:

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.