Kolo

Ο Mirko αγόρασε πρόσφατα έναν τροχό της τύχης. Έγραψε ένα κεφαλαίο γράμμα του αγγλικού αλφαβήτου σε κάθε σφήνα, όπως αυτό (3ο παράδειγμα δοκιμής):

Κανένα γράμμα δεν εμφανίζεται δύο φορές στον τροχό και ο τροχός περιστρέφεται δεξιόστροφα. Υπάρχει ένας δείκτης που παραμένει στο ίδιο σημείο ενώ ο τροχός περιστρέφεται (δείχνει το ~H~ στην παραπάνω εικόνα). Όταν περιστρέφουμε τον τροχό, το γράμμα στο οποίο δείχνει ο δείκτης αλλάζει ανάλογα.

Ο Mirko γύρισε τον τροχό ~K~ φορές στη σειρά, και κάθε φορά έγραφε πόσες φορές άλλαζε γράμμα δείχνεται και σε ποιο γράμμα δείχνονταν στο τέλος αυτής της περιστροφής.

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

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει ακέραιους αριθμούς ~N\;(2 \leq N \leq 25)~, τον αριθμό των σφηνών στον τροχό και ~K\;(1 \leq K \leq 100)~, τον αριθμό των περιστροφών.

Οι ακόλουθες ~K~ γραμμές περιέχουν περιγραφές που έγραψε ο Mirko για κάθε περιστροφή, με τη σειρά. Κάθε γραμμή περιέχει έναν ακέραιο αριθμό ~S\;(1 \leq S \leq 100)~, τον αριθμό των φορών που άλλαξε γράμμα που δείχνεται κατά τη διάρκεια αυτής της περιστροφής και ένα κεφαλαίο γράμμα στο οποίο σταμάτησε ο δείκτης.

Έξοδος

Εάν δεν υπάρχει τροχός που να πληροί τις απαιτήσεις που περιγράφονται, τυπώστε "!".

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

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

input

3 3
1 A
2 B
3 C

output

!

input

5 6
1 A
2 B
5 B
1 C
2 A
2 B

output

B?A?C

input

8 8
4 V
3 I
7 T
7 A
6 R
5 N
1 O
9 H

output

HONITAVR