#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include "heap.h"

using namespace std;

class node
{
    int freq;
    char symbol;
    const node *left;
    const node *right;

public:
		
    node(char c = 0, int i = 0)
	{
        symbol = c;
        freq = i;
        left = 0;
        right = 0;
    }

    node(const node* l, const node *r)
	{
        symbol = 0;
        freq = l->freq + r->freq;
        left = l;
        right = r;
    }

	
	bool operator>(const node &n) const
	{
        return freq > n.freq;
    }
	
    void traverse(string code = "")  const;
};


void node::traverse(string code) const
{
    if (left)
	{
        left -> traverse(code + "0");
        right -> traverse(code + "1");
    }
	else
	{
        if (symbol == '\n')
			cout << "<nl>" << "\t";
		else if (symbol == ' ')
			cout << "<space>" << "\t";
		else
			cout << symbol << "\t";
        cout << setw( 9 ) << freq;
        cout << "\t" << code << endl;
    }
}



int main()
{
    char c;
	int freq[256];
	
	// populate frequency table from standard input
	for (int i = 0 ; i < 256 ; i++)
        freq[ i ] = 0;
	while(cin.get(c))
	{
			freq[ c ]++;
	}
	
	minHeap<node> q();
    for (int i = 0 ; i < 256 ; i++)
        if (freq[ i ] )
            {
            q.push(node( i, freq[i] ));
            }	

    while (q.size > 1)
	{
		// extract first two nodes from prorioty queue
		node *left = new node( q.top() );
        q.pop();
        node *right = new node( q.top() );
        q.pop();
        
		// combine the nodes and the resulting subtree back on the priority queue
		q.push( node( left, right ) );
    }

    
	// output codes
	cout << "Symbol\tFrequency\tCode" << endl;
	cout << "------\t---------\t----" << endl;
    q.top().traverse();
    
	return 0;
}