#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
using namespace std;
class Node{
public:
	Node(char _val = ' ',int _percent = 0,bool _flag = false){
		val = _val;
		percent = _percent;
		left = NULL;
		right = NULL;
		flag = _flag;
	}
public:
	char val;
	int percent;
	Node * left;
	Node * right;
	bool flag;	
};//
void swap(Node &a, Node &b){
	Node & temp = a;
	a = b;
	b = temp;
}//

int min(vector<Node*> & _in,int _n){
	int j = 0;
	while(_in[j]->flag!=false){
		j++;
	}
	_in[j]->flag = true;
	return j;
}//获取有序最小值

void insertSort(vector<Node*> & _in,int _n){
	for(int i = 1; i < _n; i++){
		for(int j = i; j >= 1; j--){
			if(_in[j]->percent<_in[j-1]->percent){
				swap(_in[j],_in[j-1]);
			}
		}
	}	
}//
void huffman(Node * _root){
	
	if(_root != NULL){
		if(_root->val != '#')
		cout << _root->val;
		
		if(_root->left != NULL||_root->right != NULL){
			cout << '(';
			huffman(_root->left);
			if(_root->right!=NULL){
				cout << ',';
			}
			huffman(_root->right);
			cout <<')';
		}
		
	}
}//广义表形式哈弗曼树
void huffmanCode(Node * _root,int _len = 0){
	static int * save = new int[100];
	if(_root != NULL){
		if(_root->left == NULL && _root->right == NULL){
			cout << _root->val << ':';
			for(int i = 0; i < _len; i++){
				cout << save[i];
			}
			cout << endl;
		}
		else {
			save[_len] = 0;
			huffmanCode(_root->left,_len+1);
			save[_len] = 1;
			huffmanCode(_root->right,_len+1);
		}
		
		
		
	}
}//哈夫曼编码
void toFile(Node * _root, int _len = 0){
	static int * temp = new int[100];
		if(_root != NULL){
			if(_root->left == NULL && _root->right == NULL){
				ofstream p("huffman.txt",ios::app);
				if(!p) cout << "error" << endl;
					p << _root->val << ':';
				for(int i = 0; i < _len; i++){
					p << temp[i];
				}
				p << endl;
			}
			else {
				temp[_len] = 0;
				toFile(_root->left,_len+1);
				temp[_len] = 1;
				toFile(_root->right,_len+1);
			}
		}	
}//输出到文件
	
int main(int argc, char *argv[]) {
	int n = 0;
	while(cin >> n){
		// 27 A 64 B 13 C 22 D 32 E 103 F 21 G 15 H 47 I 57 J 1 K 5 L 32 M 20 N 57 O 63 P 15 Q 1 R 48 S 51 T 80 U 23 V 8 W 18 X 1 Y 16 Z 1 _ 168	C_PROGRAMME_IS_MY_FAVORITE
		// 28 A 64 B 13 C 22 D 32 E 103 F 21 G 15 H 47 I 57 J 1 K 5 L 32 M 20 N 57 O 63 P 15 Q 1 R 48 S 51 T 80 U 23 V 8 W 18 X 1 Y 16 Z 1 _ 168 * 18 C_PROGRAMME_IS_MY_FAVORITE
		vector<Node*> s;
		for(int i = 0; i < n; i++){
			char alpha = ' ';
			cin >> alpha;
			int per = 0;
			cin >> per;
			Node * p = new Node(alpha,per,false);
			s.push_back(p);
			
		}
		for(int i = 0; i < n; i++){
			cout << 	s[i]->val << "-"<< s[i]->percent << ' ';		
		}
		cout << endl;
		insertSort(s,n);
		for(int i = 0; i < n; i++){
			cout << 	s[i]->val << "-"<< s[i]->percent << '-' << s[i]->flag << ' ';		
		}
		cout << endl;
		for(int i = 0; i < n-1;i ++){
			insertSort(s,n+i);
			int j = min(s,n+i);
			int k = min(s,n+i);
			
			Node * p =new Node('#',s[j]->percent+s[k]->percent,false);
			p->left = s[j];
			p->right = s[k];
			s.push_back(p);
			
			
		}
		for(int i = 0;i < 2*n-1; i++){
			cout << s[i]->val << ':' << s[i]->percent << ' ';
		}
		cout << endl;
		huffman(s[2*n-2]);
		cout << endl;
		
		huffmanCode(s[2*n-2]);
		cout << endl;
		
		ofstream out("huffman.txt");
		out.close();
		toFile(s[2*n-2]);
		ifstream in("huffman.txt");
		
		if(!in.is_open()){
			cout << "error" << endl;
		}
		char (*res)[20] = new char[n][20];
		for(int i = 0; i < n; i++){
			for(int j = 0; j < 20; j++){
				res[i][j] = '#';
			}
		}
		
		int i = 0;
		while(!in.eof()){
			char temp[20];
			in.getline(temp, 20);
			strcpy(res[i], temp);
			i++;
			
		}
		string input = " ";
		cin >> input;
		for(int j = 0; j < input.size(); j++){
			for(int k = 0; k < n; k++){
				if(res[k][0]==input[j]){
					for(int m = 2; res[k][m]!='#';m++){
						cout << res[k][m];
					}

				}
				
			}
			cout << ' ';
			
		}
		cout << endl;		
	}
}