#include <iostream>
#include <vector>
#include <cmath>
#include <queue>
#include <map>

using namespace std;

typedef unsigned char byte;

struct Node{
    byte symbol = '-';
    int freq;
    vector<bool> path;
    int size = 0;
    int lvl = 0;
    Node* lchild = nullptr;
    Node* rchild = nullptr;
    Node(Node* _lchild, Node* _rchild) : lchild(_lchild), rchild(_rchild), freq(_rchild->freq + _lchild->freq){}
    Node(byte _symbol, int _freq) : symbol(_symbol), freq(_freq){}
    Node() = default;
    ~Node(){
        delete lchild;
        delete rchild;
    }
};

void State(Node* _node){
    queue<Node*> q;
    q.push(_node);
    Node* it;
    _node->lvl = 1;
    while(q.size()){
        it = q.front();
        if(it->lchild != nullptr){
            q.push(it->lchild);
            it->lchild->lvl = it->lvl + 1;
        }
        if(it->rchild != nullptr){
            q.push(it->rchild);
            it->rchild->lvl = it->lvl + 1;
        }
        for(int i = 0; i < it->lvl; ++i){
            cout << '\t';
        }
        cout << it->symbol << '.';
        for(int i = 0; i < it->path.size(); ++i){
            cout << it->path[i]?1:0;
        }
        cout << '\n';
        q.pop();
    }
    it = nullptr;
    cout << '\n' << '\n';
}

void FixSize(Node* _node){
    if(_node->lchild == nullptr){
        _node->size = 1;
        return;
    }
    FixSize(_node->lchild);
    FixSize(_node->rchild);
    _node->size = _node->lchild->size + _node->rchild->size + 1;
}

void CalcPath(Node* _node){
    if(_node->lchild == nullptr){
        return;
    }
    _node->lchild->path = _node->path;
    _node->lchild->path.push_back(false);
    _node->rchild->path = _node->path;
    _node->rchild->path.push_back(true);
}

byte BFSCalc(Node* _node, map<byte, vector<bool> >& mp){
    byte treeSize = 0;
    queue<Node*> q;
    q.push(_node);
    Node* it = nullptr;
    while(!q.empty()){
        it = q.front();
        q.pop();
        if(it->lchild != nullptr){
            CalcPath(it);
            q.push(it->lchild);
            q.push(it->rchild);
        }
        else{
            treeSize++;
            mp[it->symbol] = it->path;
        }
    }
    return treeSize;
}

void WriteBit(bool bit, int& bitIt, vector<byte>& outputData){
    if(bit){
        outputData.back() |= 1 << (8 - bitIt);
    }
    bitIt++;
    if(bitIt == 9){
        outputData.push_back(0);
        bitIt = 1;
    }
}

void WriteByte(byte value, int& bitIt, vector<byte>& outputData){
    bool bit;
    for(int i = 1; i < 9; ++i){
        bit = ((value >> (8 - i)) & 1 == 1);
        WriteBit(bit, bitIt, outputData);
    }
}

bool ReadBit(int& ptr, int& bitIt, vector<byte>& inputData){
    bool res = ((inputData[ptr] >> (8 - bitIt)) & 1) == 1;
    bitIt++;
    if(bitIt == 9){
        bitIt = 1;
        ptr++;
    }
    return res;
}

int main(){
    vector<byte> data;
    byte cursor;
//    int n;
//    cin >> n;
//    for(int i = 0; i < n; ++i){
//        cin >> cursor;
//        data.push_back(cursor);
//    }
    while(cin >> cursor){
        data.push_back(cursor);
    }
    vector<byte> symbols(256);
    int size = data.size();
    for(int i = 0; i < size; ++i){
        symbols[(int)data[i]]++;
    }
    vector<Node*> usedSymbols;
    int it = 0;
    Node* newNode = nullptr;
    for(int i = 0; i < 256; ++i){
        if(symbols[i] > 0){
            newNode = new Node((byte)i, symbols[i]);
            usedSymbols.push_back(newNode);
            it = usedSymbols.size() - 1;
            while(it > 0 && usedSymbols[it]->freq > usedSymbols[it - 1]->freq){
                swap(usedSymbols[it], usedSymbols[it - 1]);
                it--;
            }
        }
    }
    Node* node1;
    Node* node2;
    while(usedSymbols.size() > 1){
        node1 = usedSymbols.back();
        usedSymbols.pop_back();
        node2 = usedSymbols.back();
        usedSymbols.pop_back();
        newNode = new Node(node1, node2);
        usedSymbols.push_back(newNode);
        it = usedSymbols.size() - 1;
        while(it > 0 && usedSymbols[it]->freq > usedSymbols[it - 1]->freq){
            swap(usedSymbols[it], usedSymbols[it - 1]);
            it--;
        }
    }
    FixSize(usedSymbols[0]);
    map<byte, vector<bool> > mp;
    byte treeSize = BFSCalc(usedSymbols[0], mp);
//    State(usedSymbols[0]);
    cout << '\n';
    vector<byte> outputData;
    outputData.push_back(treeSize);
    outputData.push_back(0);
    int bitIt = 1;
    map<byte, vector<bool> >::iterator iter = mp.begin();
    for(; iter != mp.end(); ++iter){
        WriteByte(iter->first, bitIt, outputData);
        WriteByte((byte)iter->second.size(), bitIt, outputData);
        for(int i = 0; i < iter->second.size(); ++i){
            WriteBit(iter->second[i], bitIt, outputData);
        }
    }
    for(int i = 0; i < data.size(); ++i){
        for(int j = 0; j < mp[data[i]].size(); ++j){
            WriteBit(mp[data[i]][j], bitIt, outputData);
        }
    }
    outputData.push_back((byte)bitIt);
    delete usedSymbols[0];
    for(int i = 0; i < outputData.size(); ++i){
        cout << outputData[i];
    }
    vector<byte> inputData = outputData;
    int ptr = 0;
//    byte treeSize;
    treeSize = inputData[0];
    ptr++;
    byte curChar = 0;
    byte curLength = 0;
//    int bitIt = 0;
    bitIt = 1;
    Node* root = new Node;
    Node* treePtr;
    for(int i = 0; i < (int)treeSize; ++i){
        curChar = 0;
        curLength = 0;
        treePtr = root;
        for(int j = 7; j >= 0; --j){
            if(ReadBit(ptr, bitIt, inputData)){
                curChar |= 1 << j;
            }
        }
        for(int j = 7; j >= 0; --j){
            if(ReadBit(ptr, bitIt, inputData)){
                curLength |= 1 << j;
            }
        }
        for(int j = 0; j < (int)curLength; ++j){
            if(ReadBit(ptr, bitIt, inputData)){
                if(treePtr->rchild == nullptr){
                    treePtr->rchild = new Node;
                    treePtr = treePtr->rchild;
                }
                else{
                    treePtr = treePtr->rchild;
                }
            }
            else{
                if(treePtr->lchild == nullptr){
                    treePtr->lchild = new Node;
                    treePtr = treePtr->lchild;
                }
                else{
                    treePtr = treePtr->lchild;
                }
            }
        }
        treePtr->symbol = curChar;
    }
    vector<byte> result;
    treePtr = root;
//    State(root);
    while(!((ptr == inputData.size() - 2) && bitIt == (int)inputData[inputData.size() - 1])){
        while(treePtr->lchild != nullptr){
            treePtr = (ReadBit(ptr, bitIt, inputData))?treePtr->rchild:treePtr->lchild;
        }
        result.push_back(treePtr->symbol);
//        cout << treePtr->symbol;
//        cout << "here" << '\n';
        treePtr = root;
    }
    for(int i = 0; i < result.size(); ++i){
        cout << result[i];
    }
    return 0;
}