Cậu bé Fabian nhận được một bộ xếp hình một chiều gồm ~N~ mảnh ghép. Cậu nhanh chóng nhận ra rằng mỗi mảnh ghép thuộc về một trong các loại sau:

Thêm vào đó, điều đã biết là trong số ~N~ mảnh ghép đó có đúng một mảnh thuộc loại ~5~ hoặc loại ~6~ (biên trái) và đúng một mảnh thuộc loại ~7~ hoặc loại ~8~ (biên phải). Fabian muốn sắp xếp tất cả các mảnh thành một hàng sao cho mảnh đầu tiên (ở cực trái) là loại ~5~ hoặc ~6~ và mảnh cuối cùng (ở cực phải) là loại ~7~ hoặc ~8~. Hai mảnh có thể được đặt cạnh nhau chỉ khi các biên lân cận của chúng có hình dạng khác nhau, tức là một có gờ (còn được gọi là nổi hoặc tab) và một có lỗ (còn được gọi là lõm hoặc trống).

Việc giải đố đơn giản sẽ quá dễ dàng đối với Fabian nên cậu quyết định viết một số nguyên dương duy nhất lên mỗi mảnh ghép. Bây giờ cậu quan tâm đến việc tìm giải pháp nhỏ nhất từ điển cho câu đố xếp hình. Giải pháp ~A~ được coi là nhỏ hơn từ điển so với giải pháp ~B~ nếu tại vị trí đầu tiên (từ trái sang phải) ~i~ mà chúng khác nhau, giá trị được viết trên mảnh ghép thứ ~i~ trong ~A~ nhỏ hơn giá trị được viết trên mảnh ghép thứ ~i~ trong ~B~.

Lưu ý: các mảnh không thể được xoay.

Input

• Dòng đầu tiên chứa một số nguyên ~N~ ~(2 \leq N \leq 10^5)~ từ mô tả nhiệm vụ.
• ~N~ dòng tiếp theo chứa hai số nguyên ~X_i~ ~(1 \leq X_i \leq 8)~ và ~A_i~ ~(1 \leq A_i \leq 10^9)~ đại diện cho loại của mảnh ghép thứ ~i~ và số mà Fabian đã viết lên đó. Tất cả các số ~A_i~ đều khác nhau.

Output

• Nếu Fabian không thể giải câu đố xếp hình, bạn nên xuất ~−1~ trong một dòng duy nhất.
• Nếu không, bạn nên xuất các số được viết trên các mảnh trong giải pháp nhỏ nhất từ điển cho câu đố.

Chú ý

• Trong các trường hợp kiểm tra có tổng cộng ~5~ điểm, điều kiện sẽ là ~N \leq 4~.
• Trong các trường hợp kiểm tra bổ sung trị giá ~5~ điểm, điều kiện sẽ là ~N \leq 10~.
• Trong các trường hợp kiểm tra bổ sung trị giá ~10~ điểm, các mảnh của loại ~2~ và ~3~ sẽ không xuất hiện trong đầu vào.
• Trong các trường hợp kiểm tra bổ sung trị giá ~20~ điểm, sẽ có nhiều nhất một mảnh của loại ~1~ hoặc ~4~.
• Nếu đối với một trường hợp kiểm tra mà giải pháp cho câu đố tồn tại, bạn xuất câu đố được giải đúng nhưng giải pháp của bạn không phải là nhỏ nhất từ điển, bạn sẽ nhận được ~40 \%~ số điểm dự định cho trường hợp kiểm tra đó.

Sample Input 1

5
1 5
2 7
2 3
8 4
6 1

Sample Output 1

1 3 7 5 4

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

Giải thích

Trong test thứ nhất, ta thấy có hai cách giải quyết:

Chúng ta có thể thấy rằng giải pháp thứ hai được mô tả có số nhỏ hơn được viết trên mảnh thứ hai. Do đó, đó là giải pháp nhỏ nhất theo thứ tự từ điển.