/* James Little 24/4/01
   Good morning and its a marvelously cold night, the temperature is plumitting... good god its cold.
*/

package jlittle_ex8;

import java.io.*;
import java.util.*;

public class App {
    
    // data fields
    private static final int MAX =100;
    private static BufferedReader reader =
	new BufferedReader(new InputStreamReader(System.in));// get ready to read
    private static StringTokenizer tokenizedInput = new StringTokenizer(""); // start up the tokenizer
    private static String inputString = ""; // create a new string
    
    private static Vector list = new Vector();
    private static Word w;
    private static Word [] man = new Word[67];
    private static int count=0;
    private static int totalwords=0;
    
    // get last token
    public static String getLast() {  // the last one
	return inputString;
    }

    // count tokens
    public static int countTokens() {
	return tokenizedInput.countTokens();  // tokenize them tokens and tell me how many
    }

    // get integer
    public static int getInt() {
	int result = -1;
	try {
	    result = Integer.parseInt(nextToken());
	} catch (NumberFormatException e) {
	    System.out.println("Error: " + e.getMessage() +
			       " is not a valid integer");
	    System.exit(-1);
	}
	return result;
    }

    // read new line
    public static String readLine() {
	inputString = null;  // delete input
	tokenizedInput = new StringTokenizer(""); // another string tokenizer

	try {
	    inputString = reader.readLine();     
	} catch (IOException e) {
	    System.out.println("Error: " + e.getMessage());
	    System.exit(-1);  
	}
	tokenizedInput = (inputString != null) ?
	    new StringTokenizer(inputString) :
	    new StringTokenizer("");  // if true, tokenized input =  inputstring, else empty braces

	return inputString; 
    }

    // get next token
    public static String nextToken() {
	try {
	    return tokenizedInput.nextToken();
	} catch (NoSuchElementException e) {
	    System.out.println("Error: no more tokens to get.");
	    System.exit(-1);
	    return "This shouldn't be reached"; // thats for sure.. System should have exited.
	}
    }

    public static void main(String [] args){
	// start reading input
	String reads;
	int temp;
	int freq;
	while(!(reads=readLine()).equals("#")) {
	    boolean onlist=false;
	    reads=nextToken();
	    freq=getInt();
	    temp=-1;
	    try{
		
		if(reads.equals((char)92 + "u000D"))temp=13;
		else if(reads.equals((char)92 + "u0020"))temp=32;
		else if(reads.equals((char)92 + "u000A"))temp=10;
		else if(reads.equals((char)92 + "u0009"))temp=9;
		else if(reads.equals((char)92 + "u000B"))temp=11;
		else if(reads.length()==1)temp = (int)(reads.charAt(0));
		else System.out.println("ERROR: '"+reads+"' is not a valid character or Unicode String.");
	    } catch (NumberFormatException e) {
		System.out.println("ERROR: '"+reads+"' is not a valid character or Unicode String.");
	    }

	    // the reject conditions:
	    boolean reject = ((temp<32&&!(temp==13|| // exclude command char, but not carriage return
					  temp==10|| // don't exclude newline
					  temp==9|| // don't exclude horizontal tab
					  temp==11))|| // don't exclude vertical tab
			      (temp>122)|| // exclude punctuation and numbers over 127
			      (temp>32&&temp<48)|| // exclude punctuation
			      (temp>57&&temp<65)|| // exclude punctuation
			      (temp>90&&temp<97)); // exclude punctuation

	    // if(temp==-1) System.out.println("Warning : temp == -1 ERROR!");
	    for(int i = 0; i < count; i++){
		if(temp==man[i].getWord()){
		    System.out.println("ERROR: '"+reads+"' is allready in the table.");
		    onlist=true;
		}
	    }

	    if(freq>100||freq<0){
		System.out.println("ERROR: '"+freq+"' is out of range 0-100.");
		reject=true;
	    }

	    if(!reject&&!onlist){ 	  
		int index = 0;
		man[count]=new Word(temp,freq);
		totalwords+=freq;
		count++;
	    }//if
		    	       
	} //while

	
	Sort s = new Sort(man,count,totalwords);
	// get into correct order for coding
	s.quicksort(0,count-1);
	//s = new Sort(man,count,totalwords);
	int z = 0;
	int start = 0;
	boolean sorted=false;
	while(z < count){
	    if(man[start].getFreq() == man[z].getFreq()){
		z++;
	    } else {
		s.lexiSort(start,z);
		start=z;
		sorted=true;
	    }
	    		
	}
	// need to catch if roles over count with out finding differing int
	if(man[start].getFreq() == man[count-1].getFreq()) s.lexiSort(start,count);
	// need to catch if never finds differing int
	if(!sorted) s.lexiSort(0,count);
	// assign  word instances to vector
	for(int i=0; i<count; i++){
	    list.add(man[i]);
	}
	bigWords();
	code(list.size()-1);
	//for(int i = 0; i<list.size(); i++){
	//  System.out.println(i+"\t"+((Word)list.elementAt(i)).getReal()+"\t"+
	//	       ((Word)list.elementAt(i)).getWord()+"\t"+
	//	       ((Word)list.elementAt(i)).getFreq()+"\t"+
	//	       ((Word)list.elementAt(i)).getLeft()+"\t"+
	//	       ((Word)list.elementAt(i)).getRight()+"\t"+
	//	       ((Word)list.elementAt(i)).getCode());
	//}
	while(!(reads=(readLine().trim())).equals("##")) {
	    boolean found = false;
	    String fridgeMagnet=null;
	    for(int i = 0; i<list.size()-1 && !found; i++){
		if((reads.trim()).equals(((Word)list.elementAt(i)).getReal())){
		    fridgeMagnet=((Word)list.elementAt(i)).getCode();
		    found=true;
		}
	    } 
	    if(fridgeMagnet==null)fridgeMagnet="ERROR: Invalid character '"+reads+"'";
	    System.out.println(fridgeMagnet);
	}
	try{
	    while(!((reads=(readLine().trim())).equals("##"))) {
		boolean found = false;
		String fridgeMagnet=null;
		for(int i = 0; i<list.size()-1 && !found; i++){
			if((reads.trim()).equals(((Word)list.elementAt(i)).getCode())){
			    fridgeMagnet=((Word)list.elementAt(i)).getReal();
			    found=true;
			}
		}
		   if (fridgeMagnet==null) fridgeMagnet="ERROR: Invalid code '"+reads+"'";
		System.out.println(fridgeMagnet);
	    }
	}catch(NullPointerException e){
	    System.out.println("ERROR: Incomplete list.");
	}
	// ok thats it.. now for the shorts:
	System.out.println("END OF OUTPUT");
    } //main

    public static int compare(int r, int a, String bigUn, Word left){
	int z=r,i=r;
	boolean found=false;
	//System.out.println(a+"\t"+bigUn+"\t"+list.size());
	//System.out.println(((Word)list.elementAt(list.size()-2)).getFreq()+"\t"+
	//		   ((Word)list.elementAt(list.size()-2)).getReal()+"\t"+
	//		   list.size()+"\t"+(list.size()-2));
	//System.out.println(((Word)list.elementAt(list.size()-1)).getFreq()+"\t"+
	//		   ((Word)list.elementAt(list.size()-1)).getReal()+"\t"+
	//		   list.size()+"\t"+(list.size()-1));
	//System.out.println("**************\n");
	while(z < list.size()-1 && !found && a>=((Word)list.elementAt(z)).getFreq()){
	    
	    if(a==((Word)list.elementAt(z)).getFreq()&&
	     (int)bigUn.charAt(0)<((Word)list.elementAt(z)).lexidex()){
		found=true;
	    } else {
		z++;		
		i++;
	    }
	}
	if(bigUn.indexOf(((Word)list.elementAt(z)).getReal())>-1&&
	   a>=((Word)list.elementAt(z)).getFreq())i++;
	return i;
    }

    public static void bigWords(){
	int l = 0;
	int r = 1;
	while(r<list.size()){
	    boolean reset=false;
	    Word left = (Word)list.elementAt(l);
	    Word right = (Word)list.elementAt(r);
	    //System.out.println(l+"\t"+r+"\t"+list.size()+"\t"+left.getReal()+right.getReal());
	    
	    int friq = left.getFreq()+right.getFreq();
	    if(friq>((Word)list.lastElement()).getFreq()){
		list.add(new Word(left.getReal()+right.getReal(), friq, l, r, left.getWord()));
	    }else if ((left.getReal()+right.getReal()).compareTo(((Word)list.lastElement()).getReal())>0&&
		     friq==((Word)list.lastElement()).getFreq() ){
		list.add(new Word(left.getReal()+right.getReal(), friq, l, r, left.getWord()));
		//System.out.println(((Word)list.lastElement()).getReal()+
		//		   " Added to list : "+
		//		   left.getReal()+right.getReal());		
	    }else{
		int place =  compare(r,friq,left.getReal()+right.getReal(),left);
		//if(place==r){ 
		//    r++;
		//    reset=true;
		//}
		list.insertElementAt(new Word(left.getReal()+right.getReal(), friq, l, r, left.getWord()),
				     place);
	    }
	    //if(reset)r--;
	    l+=2;
	    r+=2;
	}
    }

    public static void code(int index){
	Word go = (Word)list.elementAt(index);
	if(go.getLeft()!=-1) code(go.getLeft(),0,"");
	if(go.getRight()!=-1) code(go.getRight(),1,"");
    }

    public static void code(int index,int order,String word){
	Word go = (Word)list.elementAt(index);
	go.setWord(word+order);
	if(go.getLeft()!=-1) code(go.getLeft(),0,(word+order));
	if(go.getRight()!=-1) code(go.getRight(),1,(word+order));
    }
}//App