import java.lang.*;
import java.util.*;
class lzw
{
node ar[]=new node[55];
void start()
{
String q="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ .?";
String p=null;
int ln=q.length();
for(int i=0;i<ln;i++)
{ node sj=new node();
p=q.substring(i,i+1);
sj.chkey(i);
sj.chdata(p);
ar[i]=sj;
}
}
//-----------------------------------------------------
node search1(node a,int kl)
{node rt=null;
if (a.key()==kl)
{rt=a;}
else
if(a.next()!=null)
{rt=search1(a.next(),kl);}
return rt;
}
node searchkey(int p)
{
int i=p%55;
node rt=search1(ar[i], p);
return rt;
}
//-----------------------------------------------------
node search2(node a,String w)
{node rt=null;
if (w.equals(a.data()))
{rt=a;}
else if(a.next()!=null)
{rt=search2(a.next(), w);}
return rt;
}
node searchdata(String sp)
{node rt=null;
String p=null;
if (sp.length()>1){p=sp.substring(0, 1);}
else{p=sp;}
int c=-1;
for(int i=0;i<ar.length;i++)
{if (p.equals(ar[i].data()))
{c=i;}}
if (c!=-1)
{rt=search2(ar[c], sp);}
return rt;
}
//-----------------------------------------------------
void insertat(node a,node b)
{if (a.next()==null){a.chnext(b);}
else{insertat(a.next(),b);}}
//----------------------------------------------------
void insert(node a)
{int k=a.key();
k=k%55;
insertat(ar[k],a);
}
void insert_data(node a)
{String p=a.data();
p=p.substring(0,1);
int c=0;
for(int i=0;i<ar.length;i++)
{if(p.equals(ar[i].data()))
{c=i;}}
insertat(ar[c],a);}
//-----------------------------------------------------
int sub(String jr,int i)
{int j=i+1;while( j<(jr.length()) && jr.charAt(j)!=' ' )
{j++;}
return j;}
//-----------------------------------------------------
String compress(String s)
{String w=""; String k=null; String use=null;node rt=null;
int ls=55; String ans="";int as=0;int d=0;
//------------------------
for(int i=0;i<s.length();i++)
{//-----------------
if(i<s.length()-1){k=s.substring(i,i+1);}
else{k=s.substring(i);}
//-----------------------
use =w+k;
rt=searchdata(use);
if(rt!=null)
{w=use; }
else
{
rt=searchdata(w); as=rt.key();
ans=ans+as+" ";
//--------------
node hbk=new node();
hbk.chdata(use);
hbk.chkey(ls);
ls++;
insert_data(hbk);
//----------------
w=k;
}
}
rt=searchdata(w);
String comp=ans+rt.key();
ar=null;
return comp;
}
//-----------------------------------------------------
String decompress(String ds)
{int j=sub(ds,0);String ans="";char ch;
String k=null;int wc;
//-------------------
if(j<ds.length()){k=ds.substring(0, j);}
else{k=ds.substring(0);}
int y=(new Integer(k)).intValue();
node rt=searchkey(y);
wc=y;
//------------------
ans=ans+rt.data();
ch=(rt.data()).charAt(0);
String side=null;
String side1=null;
int ls=55;
for(int i=j+1;i<ds.length();i=j+1)
//--------------------
{j=sub(ds, i);
if(j<ds.length())
{ k=ds.substring(i, j);}
else {k=ds.substring(i);}
y=(new Integer(k)).intValue();
rt=searchkey(y);
//----------------------
if(rt!=null){
side=rt.data();}
else{rt=searchkey(wc);
side=rt.data()+ch;}
ans=ans+side;
ch=side.charAt(0);
rt=searchkey(wc);
side1=rt.data()+ch;
node sf=new node();
sf.chdata(side1);
sf.chkey(ls);
insert(sf);
ls++;
wc=y;
}
ar=null;
return ans;
}
}
