슬라갈리차

어린 파비안은 $N$개의 조각으로 이루어진 1차원 직소 퍼즐을 받았다. 그는 곧 각 조각이 다음 유형 중 하나에 속한다는 것을 알아챘다.

또한 $N$개의 조각 중에는 5번 또는 6번 유형(왼쪽 경계)이 정확히 하나 있고, 7번 또는 8번 유형(오른쪽 경계)이 정확히 하나 있다.

파비안은 모든 조각을 한 줄로 배열하려고 한다. 첫 번째(가장 왼쪽) 조각은 5번 또는 6번 유형이어야 하고, 마지막(가장 오른쪽) 조각은 7번 또는 8번 유형이어야 한다. 두 조각은 맞닿는 경계의 모양이 서로 다를 때에만 나란히 놓을 수 있다. 즉 한쪽은 볼록(outie, tab)하고 다른 쪽은 오목(innie, blank)해야 한다. 조각은 회전할 수 없다.

퍼즐이 그대로면 너무 쉽다고 생각한 파비안은 각 조각에 서로 다른 양의 정수를 하나씩 적었다. 이제 그는 사전순으로 가장 작은 해를 구하고 싶어 한다. 해 A가 해 B보다 사전순으로 작다는 것은, 두 해가 처음 다른 위치 $i$에서 A의 $i$번째 조각에 적힌 수가 B의 $i$번째 조각에 적힌 수보다 작다는 뜻이다.

첫 번째 줄에 정수 $N$ ($2 \le N \le 10^5$)이 주어진다. 다음 $N$개의 줄에는 각각 두 정수 $X_i$ ($1 \le X_i \le 8$)와 $A_i$ ($1 \le A_i \le 10^9$)가 주어진다. $X_i$는 $i$번째 조각의 유형이고, $A_i$는 그 조각에 적힌 수이다. 모든 $A_i$는 서로 다르다.

퍼즐을 풀 수 없으면 한 줄에 -1을 출력한다. 풀 수 있으면 사전순으로 가장 작은 해에서 왼쪽부터 각 조각에 적힌 수를 차례대로 출력한다.

첫 번째 예제에는 가능한 해가 두 가지뿐이다(아래 그림 참고). 두 번째 해는 두 번째 조각에 적힌 수가 더 작으므로 사전순으로 가장 작은 해이다.