huffman

#include "bits/stdc++.h"
using namespace std;

#ifdef FFS
#include "debug.h"
#else
#define debug(args...)
#endif

struct node {
	char ch;
	int feq;
	node *left, *right;
	node (char _ch, int _feq) {
		ch = _ch;
		feq = _feq;
		left = right = NULL;
	}
};


map <char, string> huffman;

priority_queue <node *, vector<node *>, function <bool (const node *a, const node *b)>> pq 
	([] (const node *a, const node *b) {
		if(a ->feq == b -> feq) return a -> ch > b -> ch;
		return a -> feq > b -> feq;	
	});

node *buildTree() {
	while((int) pq.size() != 1) {
		auto left = pq.top();
		pq.pop();
		auto right = pq.top();
		pq.pop();
		node *root = new node('#', left->feq + right->feq);
		root->left = left;
		root->right = right;
		pq.push(root);
	}
	assert((int) pq.size() == 1);
	return pq.top();
}

void genCode(node *root, string now = "") {
	if(root->ch != '#') {
		huffman[root->ch] = now;
		return;
	}
	if(root->left) {
		genCode(root->left, now + "0");
	}
	if(root->right) {
		genCode(root->right, now + "1");
	}
}

signed main() {
	ios_base::sync_with_stdio(false), cin.tie(nullptr);
	int n; cin >> n;
	for(int i = 0; i < n; ++i) {
		char ch; int feq;
		cin >> ch >> feq;
		pq.push(new node (ch, feq));
	}
	genCode(buildTree());
	for(const auto &[key, val] : huffman) {
		cout << key << ' ' << val << '\n';
	}

}