Ili

Ο Mirko κατασκευάζει ένα απλό λογικό κύκλωμα στο εργαστήριό του. Το κύκλωμα αποτελείται από ~n~ καλώδια εκκίνησης που συμβολίζονται με ~x_1,\,x_2,\ldots,\,x_n~ και ~m~ λογικά στοιχεία OR που συμβολίζονται με ~c_1,\,c_2,\ldots,\,c_m~ . Κάθε στοιχείο έχει ακριβώς δύο εισόδους και μία έξοδο. Κάθε μία από τις εισόδους συνδέεται είτε με ένα καλώδιο εκκίνησης ~x_j~ είτε με την έξοδο ενός άλλου στοιχείου ~c_j~ . Φυσικά, δεν υπάρχουν κύκλοι σε ένα λογικό κύκλωμα και, επιπλέον, ισχύει ότι η είσοδος του ~c_j~ μπορεί να συνδεθεί στην έξοδο του ~c_i~ μόνο όταν ισχύει ~i < j~.
Κάθε καλώδιο εκκίνησης στο κύκλωμα μπορεί να ρυθμιστεί στην τιμή ~0~ ή ~1~ και η τιμή της εξόδου κάθε στοιχείου είναι η λειτουργία λογικής OR των εισόδων του - η τιμή είναι ~0~ εάν οι τιμές και των δύο εισόδων είναι ~0~, διαφορετικά είναι ~1~.
Ο Mirko δεν γνωρίζει τις αρχικές τιμές των καλωδίων εκκίνησης, αλλά με προσεκτικές μετρήσεις, καθόρισε τις τιμές της εξόδου ορισμένων στοιχείων. Βρείτε τις υπόλοιπες τιμές των εξόδων που μπορούν να προσδιοριστούν αναμφίβολα με βάση τις μετρήσεις.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τους θετικούς ακέραιους αριθμούς ~n~ και ~m~ - τον αριθμό των καλωδίων εκκίνησης και τον αριθμό των στοιχείων στο κύκλωμα. Η ακόλουθη γραμμή περιέχει μια συμβολοσειρά ακριβώς ~m~ χαρακτήρων που περιγράφει τη μετρούμενη τιμή της εξόδου του στοιχείου ~c_j~ ή είναι ίση με "?" αν ο Μίρκο δεν έκανε αυτή η μέτρηση.
Η ~j~-οστή από τις ακόλουθες γραμμές ~m~ περιέχει ονόματα δύο εισόδων του στοιχείου ~c_j~, το κάθε ένα είναι είτε το όνομα του καλωδίου εκκίνησης με τη μορφή "~x_i~", όπου ισχύει ~1 \le i \le n~, είτε το όνομα του στοιχείο "~c_i~", όπου ισχύει ~1 \le i < j~. Οι δύο είσοδοι του στοιχείου ~c_j~ μπορεί να είναι ίδιες. Ας υποθέσουμε ότι οι μετρούμενες τιμές είναι αμοιβαία συνεπείς.

Έξοδος

Η πρώτη γραμμή εξόδου πρέπει να περιέχει μια συμβολοσειρά ~m~ χαρακτήρων - ο ~j~-οστός χαρακτήρας στη συμβολοσειρά πρέπει να αντιστοιχεί στην τιμή της εξόδου του ~c_j~ ή να είναι "?" εάν αυτή η τιμή δεν μπορεί να προσδιοριστεί με βεβαιότητα.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	7	~n \le 15,\,m \le 20~
2	42	~n \le 500,\,m \le 500~
3	51	~ n \le 10\,000,\,m \le 10\,000~
4	15	~ 1 \le N \le 500~

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

input

4 4
10??
x1 x2
x2 x3
x3 x4
x1 c3

output

10?1

input

4 5
11???
x1 x2
x3 x4
x1 x3
x2 x4
c3 c4

output

11??1