Matrica

Ένας πίνακας (matrix) είναι ένας ορθογώνιος πίνακας γραμμάτων. Ένας τετραγωνικός πίνακας είναι ένας πίνακας με ίσο αριθμό σειρών και στηλών. Ένας τετραγωνικός πίνακας ~M~ ονομάζεται συμμετρικός εάν τα γράμματά του είναι συμμετρικά ως προς την κύρια διαγώνιο (~M_{ij} = M_{ji}~ για όλα τα ζεύγη των ~i~ και ~j~).
Το παρακάτω σχήμα δείχνει δύο συμμετρικούς πίνακες και έναν που δεν είναι συμμετρικός:

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

Είσοδος

Η πρώτη γραμμή της εισόδου περιέχει δύο ακέραιους ~N (1 \le N \le 30\,000)~ και ~K (1 \le K \le 26)~. ~N~ είναι η διάσταση του πίνακα, ενώ ~K~ είναι ο αριθμός των διακριτών γραμμάτων που θα εμφανιστούν.
Κάθε μία από τις ακόλουθες ~K~ γραμμές περιέχει ένα κεφαλαίο γράμμα και έναν θετικό ακέραιο, που χωρίζονται με ένα κενό. Ο ακέραιος υποδηλώνει πόσα αντίστοιχα γράμματα πρέπει να χρησιμοποιηθούν. Για παράδειγμα, εάν μια γραμμή λέει "~A 3~", τότε το γράμμα ~A~ πρέπει να εμφανίζεται τρεις φορές στον πίνακα εξόδου.
Ο συνολικός αριθμός των γραμμάτων θα είναι ακριβώς ~N^2~. Κανένα γράμμα δεν θα εμφανίζεται περισσότερες από μία φορές στην είσοδο.
Η επόμενη γραμμή περιέχει έναν ακέραιο αριθμό ~P (1 \le P \le 50)~, τον αριθμό των στηλών που πρέπει να τυπώθούν.
Η τελευταία γραμμή περιέχει ~P~ ακέραιους αριθμούς, τους δείκτες των στηλών που πρέπει να τυπωθούν. Οι δείκτες θα είναι μεταξύ ~1~ και ~N~, κλειστό διάστημα ~[1,\;N]~, και δίνονται με αύξουσα σειρά και χωρίς διπλότυπα.

Έξοδος

Εάν είναι δυνατό να συνθέσετε έναν συμμετρικό πίνακα από τη δεδομένη συλλογή γραμμάτων, τυπώστε τις απαιτούμενες στήλες σε ~N~ γραμμές και η καθεμία περιέχει ~P~ χαρακτήρες, χωρίς κενά. Διαφορετικά, τυπώστε "IMPOSSIBLE" (τα εισαγωγικά είναι για σαφήνεια).

Βαθμολογία

Στα αρχεία ελέγχου αξίας ~60%~ των πόντων, το ~N~ θα είναι το πολύ ~300~.
Στα αρχεία ελέγχου αξίας ~80%~ των πόντων, το ~N~ θα είναι το πολύ ~3\,000~.

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

input

3 3
A 3
B 2
C 4
3
1 2 3

output

AAB
ACC
BCC

input

4 4
A 4
B 4
C 4
D 4
4
1 2 3 4

output

AABB
AACC
BCDD
BCDD

input

4 5
E 4
A 3
B 3
C 3
D 3
2
2 4

output

AC
BE
DE
ED

input

4 6
F 1
E 3
A 3
B 3
C 3
D 3
4
1 2 3 4

output

IMPOSSIBLE