Fliper

Ο Mirko και ο Slavko βρήκαν τυχαία ένα παλιό φλιπεράκι. Το παιχνίδι αποτελείται από μια μικρή μεταλλική μπάλα που κινείται μέσα στο μηχάνημα, χτυπώντας και αναπηδώντας από κάποια εμπόδια.

Το παιχνίδι λαμβάνει χώρα σε έναν πίνακα που αντιπροσωπεύεται από ένα επίπεδο, και ~n~ εμπόδια δίνονται σε αυτό το επίπεδο. Ένα εμπόδιο αντιπροσωπεύεται από ένα ευθύγραμμο τμήμα μοναδιαίου μήκους που έχει κλίση σε γωνία ~45~° σε σχέση με τους άξονες συντεταγμένων. Ένα εμπόδιο περιγράφεται μοναδικά από τη θέση του μέσου σημείου του ~(x_i,\;y_i)~ και από έναν χαρακτήρα ο οποίος είναι είτε "/" είτε "\", που υποδηλώνει τον προσανατολισμό του εμποδίου. Στον πίνακα υπάρχει και μπάλα που κινείται σε μία από τις τέσσερις κατευθύνσεις παράλληλα προς τους άξονες, ανά πάσα στιγμή. Αν η μπάλα χτυπήσει σε εμπόδιο, η φορά της κίνησής της αλλάζει κατά ~90~° και η μπάλα συνεχίζει να κινείται. Σημειώστε ότι τα εμπόδια είναι διπλής όψης, που σημαίνει ότι η μπάλα μπορεί να αναπηδήσει και από τις δύο πλευρές του εμποδίου. Ο Mirko και ο Slavko αποφάσισαν να αποκαταστήσουν το φλιπεράκι με μια νέα στρώση χρώματος. Στη διάθεσή τους είναι τέσσερις κουβάδες χρώματος που περιέχουν τέσσερα διαφορετικά χρώματα. Θέλουν να ζωγραφίσουν κάθε εμπόδιο σε ένα από τα τέσσερα χρώματα.

Mirko: "Ξέρεις, το σκέφτηκα. Υπάρχουν μόνο δύο πιθανότητες για το μονοπάτι που θα μπορούσε να ακολουθήσει η μπάλα".

Slavko: "Τι εννοείς;"

Mirko: "Λοιπόν, είτε η μπάλα θα κολλήσει σε έναν κύκλο, επαναλαμβάνοντας περιοδικά την ίδια σειρά αναπηδήσεων, ή κάποια στιγμή θα φύγει στο άπειρο".

Slavko: "Χμ, έχεις δίκιο. Τότε ίσως θα μπορούσαμε να προσπαθήσουμε να χρωματίσουμε τα εμπόδια έτσι ώστε για κάθε κύκλο το κάθε χρώμα να εμφανίζεται ίσες φορές στον κύκλο έτσι ώστε ο αριθμός αυτός να είναι άρτιος. Για παράδειγμα, αν κάποιος κύκλος αποτελείται από 24 αναπηδήσεις, θα πρέπει να τον κάνουμε έτσι ώστε να υπάρχουν 6 αναπηδήσεις για κάθε χρώμα και το 6 είναι ένας ζυγός αριθμός."

Mirko: "Και αν δεν υπάρχει τέτοιος χρωματισμός;"

Slavko: "Ξέρεις τη διαδικασία, απλά πες -1."

Βοηθήστε τον Mirko και τον Slavko να καθορίσουν έναν χρωματισμό των εμποδίων που ικανοποιεί την απαιτούμενη προϋπόθεση, εάν υπάρχει.

Είσοδος

Η πρώτη γραμμή περιέχει έναν θετικό ακέραιο ~n\;(1 \le n \le 500\,000)~, τον αριθμό των εμποδίων.

Η ~i~-οστή των επόμενων ~n~ γραμμών περιέχει ακέραιους αριθμούς ~x_i~ και ~y_i\;(0 \le |x_i|, |y_i| \le 10^9)~ και έναν χαρακτήρα ~c_i~ ('/' ή '\') που περιγράφουν το ~i~-οστό εμπόδιο. Κανένα εμπόδιο δεν έχει την ίδια θέση.

Έξοδος

Εάν δεν υπάρχει χρωματισμός που να ικανοποιεί την απαιτούμενη προϋπόθεση, στη μοναδική γραμμή εξόδου εκτυπώστε -1.

Διαφορετικά, στη μοναδική γραμμή εξόδου εκτυπώστε μια ακολουθία από ~n~ αριθμούς ~1,\;2,\;3~ ή ~4~ που χωρίζονται με κενά, που αντιπροσωπεύουν έναν έγκυρο χρωματισμό, τα χρώματα των εμποδίων με τη σειρά. Εάν υπάρχουν περισσότερες από μία λύσεις, εκτυπώστε όλες τις λύσεις.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	20	~1 \le n \le 40~
2	20	Υπάρχει το πολύ ένας κύκλος στον οποίο η μπάλα μπορεί να κολλήσει.
3	70	Κανένας επιπλέον περιορισμός.

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

input

4
1 1 \
3 1 /
3 2 \
1 2 /

output

-1

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

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

input

9
1 2 \
1 3 /
2 1 \
2 2 \
2 3 \
3 1 /
3 2 \
4 2 /
4 3 \

output

1 3 2 4 1 3 2 4 1

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

Υπάρχει μόνο ένας κύκλος στον οποίο η μπάλα μπορεί να κολλήσει. Η παρακάτω εικόνα δείχνει έναν έγκυρο χρωματισμό. Εκκίνηση από το εμπόδιο 1, κινούμενος προς τη φορά των δεικτών του ρολογιού, τα χρώματα επαναλαμβάνονται ~1\;3\;1\;4\;2\;3\;2\;4~.