Slagalica

Ο μικρός Fabian απέκτησε ένα μονοδιάστατο παζλ που αποτελείται από ~N~ κομμάτια. Γρήγορα συνειδητοποίησε ότι κάθε κομμάτι ανήκει σε έναν από τους παρακάτω τύπους:

Επιπλέον, είναι γνωστό ότι μεταξύ αυτών των κομματιών ~N~ υπάρχει ακριβώς ένα κομμάτι είτε τύπου 5 είτε τύπου 6 (αριστερό περίγραμμα) και ακριβώς ένα κομμάτι είτε τύπου 7 είτε τύπου 8 (δεξιό περίγραμμα).

Ο Fabian επιθυμεί να τακτοποιήσει όλα τα κομμάτια σε μια ενιαία σειρά έτσι ώστε το πρώτο (αριστερό) κομμάτι να είναι τύπου 5 ή 6 και το τελευταίο (δεξιά) του τύπου 7 ή 8. Δύο κομμάτια μπορούν να τοποθετηθούν το ένα δίπλα στο άλλο εάν και μόνο εάν τα γειτονικά τους περιγράμματα έχουν διαφορετικά σχήματα, δηλαδή, το ένα έχει ένα εξόγκωμα (ονομάζεται outie ή tab) και το άλλο έχει μια τρύπα (ονομάζεται innie ή blank).

Η απλή επίλυση του παζλ θα ήταν πολύ εύκολη για τον Fabian και έτσι αποφάσισε να γράψει έναν μοναδικό θετικό ακέραιο σε κάθε κομμάτι. Τώρα τον ενδιαφέρει να βρει τη λεξικογραφικά μικρότερη λύση στο παζλ. Η λύση ~A~ θεωρείται λεξικογραφικά μικρότερη από τη λύση ~B~ εάν στην πρώτη θέση (από αριστερά) ~i~ όπου διαφέρουν ισχύει ότι ο αριθμός που γράφτηκε στο i-οστό παζλ στο ~A~ είναι μικρότερος από τον αριθμό που γράφτηκε στο i-οστό παζλ στο ~B~.

Σημείωση: τα κομμάτια δεν περιστρέφονται.

Είσοδος

Η πρώτη γραμμή περιέχει έναν ακέραιο ~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)~ που αντιπροσωπεύουν τον τύπο του i-οστού κομματιού και τον αριθμό που έγραψε σε αυτό ο Fabian. Όλοι οι αριθμοί ~A_i~ θα είναι διαφορετικοί.

Έξοδος

Εάν ο Fabian δεν μπορεί να λύσει το παζλ, θα πρέπει να εξάγετε -1 σε μία γραμμή.

Διαφορετικά, θα πρέπει να βγάλετε τους αριθμούς που είναι γραμμένοι στα κομμάτια στη λεξικογραφικά μικρότερη λύση του παζλ.

Βαθμολογία

Σε δοκιμαστικές περιπτώσεις συνολικής αξίας 5 βαθμών θα ισχύει ~N \le 4~.
Σε δοκιμαστικές περιπτώσεις αξίας επιπλέον 5 βαθμών θα έχει ~N \le 10~.
Σε δοκιμαστικές περιπτώσεις αξίας επιπλέον 10 πόντων, τα κομμάτια των τύπων 2 και 3 δεν θα εμφανίζονται στην είσοδο.
Σε δοκιμαστικές περιπτώσεις αξίας επιπλέον 20 πόντων θα υπάρχει το πολύ ένα κομμάτι τύπου 1 ή 4.

Εάν για κάποια δοκιμαστική περίπτωση στην οποία υπάρχει η λύση του παζλ, βγάζετε το σωστά λυμένο παζλ αλλά η λύση σας δεν είναι λεξικογραφικά μικρότερη, θα λάβετε το 40% των πόντων που προορίζονται για αυτήν την περίπτωση δοκιμής.

Παραδείγματα

input

5
1 5
2 7
2 3
8 4
6 1

output

1 3 7 5 4

Επεξήγηση του 1ου παραδείγματος:

Υπάρχουν μόνο δύο πιθανές λύσεις στο παζλ:

Μπορούμε να δούμε ότι η δεύτερη απεικονιζόμενη λύση έχει έναν μικρότερο αριθμό γραμμένο στο δεύτερο κομμάτι. Επομένως, αυτή είναι η λεξικογραφικά μικρότερη λύση.

input

3
5 1
7 2
4 3

output

1 3 2

input

5
2 5
2 7
2 3
8 4
6 1

output

-1