#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

struct treenode{
    int num;
    int freq;
    vector<int> code;
    string codeStr;  // !
    struct treenode *parent;
    struct treenode *leftchild;
    struct treenode *rightchild;
};

bool CompareFreq(treenode *a,treenode *b){return a->freq < b->freq;};
void HuffmanCoding();
void HuffmanEncode(int n , treenode *root);
void BuildHuffmanCode(treenode *root, string parentCode );
void PrintCode(treenode *root);

int main()
{
   HuffmanCoding();
}

void HuffmanCoding(){
    int n;
    cin >> n;
    vector<treenode *> vector;
    for(int i = 0 ; i < n ; i++){
        treenode *tempnode = new treenode;
        tempnode->num = i;  // !
        tempnode->codeStr = "";
        tempnode->parent = NULL;  // ! 後面有要用NULL判斷，初始化保險
        tempnode->leftchild = NULL;  // ! 後面有要用NULL判斷，初始化保險
        tempnode->rightchild = NULL;  // ! 後面有要用NULL判斷，初始化保險
        cin >> tempnode->freq;
        vector.push_back(tempnode);
    }
    sort(vector.begin(),vector.end(),CompareFreq);

    int count = 0;
    while(count < n-1){
    	// treenode *tempnode1 = new treenode;  tempnode1 = vector[0];  // ! 浪費一格空間
        // treenode *tempnode2 = new treenode;  tempnode2 = vector[1];  // ! 浪費一格空間
        treenode *tempnode1;  tempnode1 = vector[0];
        treenode *tempnode2;  tempnode2 = vector[1];
		treenode *insertnode = new treenode; // ! 沒有格子放資訊
        insertnode->num;
        insertnode->codeStr = "";  // !
        insertnode->freq = tempnode1->freq + tempnode2->freq;
        insertnode->leftchild = tempnode1;
        insertnode->rightchild = tempnode2;
        tempnode1->parent = insertnode ; tempnode2->parent = insertnode;
        vector[1] = insertnode;
        vector.erase(vector.begin());
        sort( vector.begin(), vector.end(), CompareFreq );
        count ++; // ! 原本沒有這行

    }

    // treenode *root = new treenode; root = vector[0]; // ! 浪費一格空間
    treenode *root = vector[0];
    HuffmanEncode(n , root);

}

void HuffmanEncode(int n , treenode *root){
    BuildHuffmanCode(root, root->codeStr);
    PrintCode(root);
}

void BuildHuffmanCode(treenode *root, string parentCode ){
	// ! 條件怪怪的 root會進去1和2，code應該是跟著child，不是跟著parent

    // treenode *root_parent = new treenode;  root_parent = root->parent; // ! 浪費一格空間
    treenode *root_parent = root->parent;
    if(root->leftchild != NULL){
        root->leftchild->codeStr = root->codeStr + "0";
        BuildHuffmanCode(root->leftchild, root->codeStr );
    }
    if(root->rightchild != NULL){
        root->rightchild->codeStr = root->codeStr + "1";
        BuildHuffmanCode(root->rightchild, root->codeStr );
    }
    if(root->leftchild == NULL && root->rightchild == NULL){
		return;
	}
}

void PrintCode(treenode *root){
    queue<treenode *> queue;
    queue.push(root);
    while (!queue.empty()){                     // 若queue不是空的, 表示還有node沒有visiting
        treenode *current = queue.front();      // 取出先進入queue的node
        queue.pop();
        for(int i = 0 ; i < current->code.size() ; i++){
        	for ( int k = 0; k < current->code.size(); k ++ ); // cout << current->code[k] << " ";   // 進行visiting  // !
        }

		cout << current->freq << " " << current->codeStr << endl;
        if (current->leftchild != NULL){    // 若leftchild有資料, 將其推進queue
            queue.push(current->leftchild);
        }
        if (current->rightchild != NULL){   // 若rightchild有資料, 將其推進queue
            queue.push(current->rightchild);
        }
    }
}