#include <iostream>
#include <stack>
using namespace std;
struct Node{
int a;
int parent;
int left;
int right;
};
void show(stack<int> s)
{
if(s.empty())return;
int t=s.top();
s.pop();
show(s);
cout<<t;
}
stack<int> s;
void Code(Node * p,int size,char * q)
{
if(p[size].left==-1&&p[size].right==-1)
{
cout<<q[size]<<" Code :";
show(s);
cout<<endl;
return;
}
s.push(1);
Code(p,p[size].left,q);
s.pop();
s.push(0);
Code(p,p[size].right,q);
s.pop();
}
void main()
{
int size;
cin>>size;
Node * p=new Node[size*2-1];
for(int i=0;i!=size*2-1;++i)
{
p[i].a=0;
p[i].parent=p[i].left=p[i].right=-1;
}
char * q=new char[size];
for(int i=0;i!=size;++i)
{
cin>>q[i]>>p[i].a;
}
for(int i=0;i!=size-1;++i)
{
int bound=size-1+i;
int min1=-1,min2=-1;
for(int j=0;j<=bound;++j)
{
if(p[j].parent==-1&&min1==-1)
min1=j;
else if(p[j].parent==-1&&min2==-1)
{
if(p[j].a>p[min1].a)
min2=j;
else
{
min2=min1;
min1=j;
}
}
else if(p[j].parent==-1&&p[j].a<p[min2].a && p[min1].a<p[j].a)
min2=j;
else if(p[j].parent==-1&&p[j].a<p[min1].a )
{
min2=min1;min1=j;
}
}
p[min1].parent=bound+1;p[min2].parent=bound+1;
p[bound+1].left=min1;
p[bound+1].right=min2;
p[bound+1].a=p[min1].a+p[min2].a;
}
Code(p,2*size-2,q);
::system("pause");
}
