Kovanice

Ο Mirko έκανε μια τουριστική επίσκεψη σε μια μακρινή χώρα όπου δεν χρησιμοποιούνται χαρτονομίσματα, αλλά μόνο κέρματα. Ακριβέστερα, η χώρα έχει ~N~ τύπους νομισμάτων σε κυκλοφορία. Τα ονόματά τους είναι, αντίστοιχα, '~K1~','~K2~', '~K3~', ~\cdots~, '~KN~'. Τα νομίσματα έχουν το ίδιο μέγεθος και σχήμα, αλλά διαφορετικά βάρη. Το '~K1~' είναι ο ελαφρύτερος τύπος κέρματος, το '~K2~' είναι το δεύτερο ελαφρύτερο και ούτω καθεξής μέχρι τον βαρύτερο τύπο '~KN~'.
Ο Mirko έχει ~M~ κέρματα στην τσέπη του, αλλά δεν ξέρει ποιο είναι ποιου τύπου. Προκειμένου να το καθορίσει, έχει στη διάθεσή του μόνο μια απλή ζυγαριά.
Αρχικά, ο Mirko σημάδεψε τα άγνωστα νομίσματά του με αριθμούς από το ~1~ έως το ~M~ και στη συνέχεια έκανε ~V~ ζυγίσματα. Σε κάθε ζύγισμα, έβαζε ένα νόμισμα στη μια πλευρά της ζυγαριάς και ένα άλλο νόμισμα στην άλλη πλευρά της ζυγαριάς. Μετά είδε αν τα δύο νομίσματα ζυγίζουν ίσα και αν δεν, ποιο είναι βαρύτερο.
Γράψτε ένα πρόγραμμα που, με βάση τα αποτελέσματα της ζύγισης, θα προσδιορίζει τον τύπο του κέρματος για κάθε κέρμα που είναι δυνατό να προσδιοριστεί μοναδικά.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει ακέραιους αριθμούς ~N~,\,~M~ και ~V~ - ο αριθμός των τύπων νομισμάτων στη χώρα, ο αριθμός των νομισμάτων στην τσέπη του Mirko και ο αριθμός των ζυγισμάτων.
Κάθε μία από τις ακόλουθες γραμμές ~V~ περιέχει το αποτέλεσμα μιας ζύγισης με τη μορφή ~ACB~ όπου οι \(Α\) και \(Β\) είναι διαφορετικοί ακέραιοι μικρότεροι ή ίσοι του ~M~ , και ο ~C~ είναι ο χαρακτήρας '~-~' (ίσον) ή '~<~' (λιγότερο).
Δεν υπάρχει κενό μεταξύ των αριθμών και του χαρακτήρα ~C~. Το αποτέλεσμα μιας ζύγισης μας λέει ότι το κέρμα του Mirko που σημειώνεται με ~A~ έχει ίσο βάρος με το νόμισμα που σημειώνεται με ~B~ ή είναι ελαφρύτερο από αυτό.
Τα αποτελέσματα της ζύγισης δεν θα είναι αντιφατικά.

Έξοδος

Εκτυπώστε ~M~ γραμμές. Η γραμμή ~i~ πρέπει να περιέχει τον τύπο του νομίσματος που σημειώνεται με ~i~ - μια ακολουθία χαρακτήρων της μορφής '~KX~' όπου το ~X~ είναι ένας ακέραιος αριθμός μεταξύ ~1~ και ~N~.
Εάν δεν είναι δυνατόν ο μοναδικός προσδιορισμός του βάρους του νομίσματος που σημειώνεται με ~i~, πληκτρολογήστε τον χαρακτήρα '~?~' στην ~i~-οστή γραμμή.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	10	~N = 2,\,1 \le M \le 1\,000~
2	40	~N = 2,\,1\le M \le 300\,000~
3	10	~ 1 \le M \le 1\,000~
4	40	~ 1 \le M \le 300\,000~

Σε όλα τα υποπροβλήμαρα, θα ισχύει ~2 \le N \le 300\,000~ και ~1 \le V \le 300\,000~.

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

input

3 5 3
1<2
2<4
3=5

output

K1
K2
?
K3
?

input

2 7 6
1=2
2=3
2=7
3<4
4=5
4=6

output

K1
K1
K1
K2
K2
K2
K1