Huffman Encoding

Υπάρχει ένας έξυπνος αλγόριθμος συμπίεσης κειμένου που ονομάζεται κωδικοποίηση Huffman και σχεδιάστηκε από τον David Huffman το 1952.

Η βασική ιδέα είναι ότι κάθε χαρακτήρας συνδέεται με μια δυαδική ακολουθία (δηλαδή μια ακολουθία από ~0~ και ~1~). Αυτές οι δυαδικές ακολουθίες ικανοποιούν την prefix-free ιδιότητα: μια δυαδική ακολουθία για έναν χαρακτήρα δεν είναι ποτέ πρόθεμα(prefix) της δυαδικής ακολουθίας ενός άλλου χαρακτήρα.

Αξίζει να σημειωθεί ότι για να κατασκευάσετε μια δυαδική ακολουθία prefix-free, απλά τοποθετήστε τους χαρακτήρες ως φύλλα ενός δυαδικού δέντρου και χαρακτηρίστε την "αριστερή" ακμή με ~0~ και τη "δεξιά" ακμή με ~1~. Το μονοπάτι από τη ρίζα σε έναν κόμβο φύλλου αποτελεί τον κώδικα για τον χαρακτήρα σε αυτόν τον κόμβο φύλλου. Για παράδειγμα, το ακόλουθο δυαδικό δέντρο συγκροτεί μια prefix-free δυαδική ακολουθία για τους χαρακτήρες {~A~, ~B~, ~C~, ~D~, ~E~}:

Δηλαδή, το ~A~ κωδικοποιείται ως ~00~, το ~B~ κωδικοποιείται ως ~01~, το ~C~ κωδικοποιείται ως ~10~, το ~D~ κωδικοποιείται ως ~110~ και το ~E~ κωδικοποιείται ως ~111~.

Το πλεονέκτημα ενός συνόλου κωδικοποιήσεων που έχουν την prefix-free ιδιότητα είναι ότι οποιαδήποτε ακολουθία αυτών των κωδικοποιήσεων μπορεί να αποκωδικοποιηθεί με μοναδικό τρόπο στους αρχικούς χαρακτήρες.

Η δουλειά σας είναι να διαβάσετε μια κωδικοποίηση Huffman (δηλ. ένα σύνολο χαρακτήρων και σχετικών δυαδικών ακολουθιών) μαζί με μια δυαδική ακολουθία και να αποκωδικοποιήσετε τη δυαδική ακολουθία στην αναπαράσταση των χαρακτήρων της.

Είσοδος

Η πρώτη γραμμή της εισόδου θα είναι ένας ακέραιος αριθμός ~k\;(1 \le k \le 20)~, που αντιπροσωπεύει τον αριθμό των χαρακτήρων και σχετικών κωδικοποιήσεων. Οι επόμενες ~k~ γραμμές περιέχουν έναν χαρακτήρα η καθεμία, ακολουθούμενο από ένα κενό διάστημα, ακολουθούμενο από τη δυαδική ακολουθία (μήκους το πολύ ~10~) που αντιπροσωπεύει την σχετική κωδικοποίηση αυτού του χαρακτήρα. Μπορείτε να υποθέσετε ότι ο χαρακτήρας είναι χαρακτήρας του αλφαβήτου (δηλαδή, 'a'...'z' και 'A'...'Z'). Μπορείτε να υποθέσετε ότι η ακολουθία των δυαδικών κωδικοποιήσεων έχει την prefix-free ιδιότητα. Στην ~k + 2~-οστή γραμμή είναι η δυαδική ακολουθία που πρέπει να αποκωδικοποιηθεί. Μπορείτε να υποθέσετε ότι η δυαδική ακολουθία περιέχει κωδικοποιήσεις που σχετίζονται με τους δεδομένους χαρακτήρες και ότι η ~k + 2~-οστή γραμμή δεν περιέχει περισσότερα από ~250~ δυαδικά ψηφία.

Έξοδος

Σε μία γραμμή, να εξάγετε τους χαρακτήρες που αντιστοιχούν στη δεδομένη δυαδική ακολουθία.

Παράδειγμα

input

5
A 00
B 01
C 10
D 110
E 111
00000101111

output

AABBE