Superpozicija

Ο παγκοσμίου φήμης φυσικός Juraj ανακάλυψε πρόσφατα ένα νέο είδος στοιχειώδους σωματιδίου - το "παρενθέσιο". Ένα "παρενθέσιο" μπορεί να έχει είτε μια ανοιχτή "(" ή ")" κλειστή διαμόρφωση. Χρησιμοποιώντας τον αυτοσχέδιο επιταχυντή σωματιδίων του, ο Juraj έχει δημιουργήσει ~t~ ακολουθίες υπερθέσεων ~n~ "παρενθέσιων". Σε καθεμία από τις ακολουθίες ~t~ υπάρχουν ~n~ "παρενθέσια" σε μια υπερθέση μεταξύ δύο διαφορετικών θέσεων και (όχι απαραίτητα διαφορετικών) διαμορφώσεων. Εάν παρατηρηθεί η ακολουθία, η κυματοσυνάρτηση των παρενθέσεων καταρρέει και καθένα από αυτά καταλήγει σε μία από τις πιθανές θέσεις και διαμορφώσεις του. Ο Juraj θέλει να μάθει αν είναι δυνατόν τα "παρενθέσια" να συμπτύσσονται σε μια έγκυρη ακολουθία παρενθέσεων.

Ο Juraj M. PhD γνωρίζει ότι η κβαντική φυσική αυτών των επαναστατικών, και πλήρως επιστημονικά θεμελιωμένων σωματιδίων, είναι πολύ πάνω από τις δυνατότητες ενός μέσου διαγωνιζόμενου του COCI, οπότε έδωσε μια επίσημη δήλωση εργασίας:

Σας δίνονται ~t~ ακολουθίες ~2n~ ανοικτών και κλειστών παρενθέσεων. Κάθε παρένθεση είναι μέλος ακριβώς ενός ζεύγους παρενθέσεων. Δύο παρενθέσεις μέσα σε ένα ζεύγος μπορεί να είναι διαφορετικές, και οι δύο ανοιχτές ή και οι δύο κλειστές. Ο Juraj θέλει να μάθει αν είναι δυνατό να επιλέξει μία μόνο παρένθεση από κάθε ένα από τα ζεύγη έτσι ώστε οι επιλεγμένες παρενθέσεις να σχηματίζουν μια έγκυρη ακολουθία παρενθέσεων. Επιπλέον, αν αυτό είναι εφικτό, σας ζητά να εκτυπώσετε ποιες παρενθέσεις πρέπει να επιλέξει για να λάβει μια έγκυρη ακολουθία. Μια ακολουθία παρενθέσεων είναι έγκυρη εάν είναι κενή ή μπορεί να γραφτεί ως ~(A)~ ή ~AB~ όπου τα ~A~ και ~B~ είναι αυθαίρετες έγκυρες ακολουθίες παρενθέσεων.

Είσοδος

Η πρώτη γραμμή περιέχει έναν ακέραιο ~t\;(1 \le t \le 100\,000)~, αριθμό ακολουθιών παρενθέσεων. Ακολουθεί η περιγραφή των ~t~ ακολουθιών.

Η πρώτη γραμμή της περιγραφής ακολουθίας περιέχει έναν ακέραιο ~n\;(1 \le n \le 100\,000)~, αριθμό ζευγών παρενθέσεων στην ακολουθία.

Η δεύτερη γραμμή περιέχει το ~z~, μια συμβολοσειρά μήκους ~2n~. Το ~z~ περιέχει αποκλειστικά χαρακτήρες "(" και ")".

Οι ακόλουθες ~n~ γραμμές περιγραφής ακολουθίας περιέχουν δύο ακέραιους αριθμούς ~a_i~ και ~b_i\;(1 \le a_i < b_i \le 2n)~. Καθένας από τους αριθμούς ~1,\;2,\;\ldots,\;2n~ εμφανίζεται ακριβώς μία φορά.

Το άθροισμα όλων των n θα είναι μικρότερο ή ίσο με ~100\,000~.

Έξοδος

Στην ~i~-οστή των ~t~ γραμμών εκτυπώστε μια ακολουθία από μηδέν και ένα που αντιπροσωπεύουν μια πιθανή επιλογή παρενθέσεων. Αν οι παρενθέσεις με δείκτη ~a_j~ του ~j~-οστού ζεύγους της ~i~-οστής ακολουθίας επιλεχθούν, εκτυπώνετε 0, διαφορετικά εάν επιλεχθεί η παρένθεση με δείκτη ~b_j~, εκτυπώστε 1. Εάν δεν υπάρχει έγκυρη ακολουθία παρενθέσεων, εκτυπώστε -1.

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

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	10	~1 \le n \le 10~
2	10	~z[a_i] = z[b_i]~ για όλα τα ~i\;=\;1,\;2,\;\ldots,\;n~.
3	20	~b_i\;=\;a_i + 1~ for all ~i\;=\;1,\;2,\;\ldots,\;n~.
4	70	Κανένας επιπλέον περιορισμός.

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

input

1
4
()))((()
1 2
3 5
4 6
7 8

output

0 1 0 1

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

Από την αρχική ακολουθία ( ) ) ) ( ( ( ), θα παραμείνουν μόνο οι έντονες παρενθέσεις ( ) ) ) ( ( ( ). Δηλαδή ( ) ( ), που είναι έγκυρη ακολουθία παρενθέσεων.

input

1
4
)()()()(
1 2
3 4
5 6
7 8

output

1 1 0 0

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

Από την αρχική ακολουθία ) ( ) ( ) ( ) (, θα παραμείνουν μόνο οι έντονες παρενθέσεις ) ( ) ( ) ( ) (. Δηλαδή ( ( ) ), που είναι έγκυρη ακολουθία παρενθέσεων.

input

1
3
(()())
1 6
2 4
3 5

output

-1