#include <fstream>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;

struct Node {
    char code = NULL;
    int w = 0;
    Node *parent = NULL;
    Node *left = NULL;
    Node *right = NULL;
};

void updateWeight(Node *root) {
    root->w++;
    if (root->parent != NULL)
        updateWeight(root->parent);
}

void updateChildren(Node *parent) {
    if (parent->left->w > parent->right->w) {
        swap(parent->left, parent->right);
    }
}

void switchNodes(Node *n1, Node *n2) {
    if (n1->parent->left == n1) {
        n1->parent->left = n2;
    } else {
        n1->parent->right = n2;
    }

    if (n2->parent->left == n2) {
        n2->parent->left = n1;
    } else {
        n2->parent->right = n1;
    }

    swap(n1->parent, n2->parent);
    updateChildren(n1->parent);
}

void recount(Node *escp) {
    if (escp != NULL) {
        escp->w = escp->left->w + escp->right->w;
        recount(escp->parent);
    }
}


vector<Node *> sortTree(vector<Node *> tree) {
    bool n = false;
    int ind;
    for (int i = tree.size() - 1; i > 0; i--) {
        for (int j = i - 1; j > -1; j--) {
            if (tree[i]->w > tree[j]->w) {
                n = true;
                ind = j;
            }
        }
        if (n) {
            switchNodes(tree[i], tree[ind]);
            swap(tree[i], tree[ind]);
            break;
        }
    }
    return tree;
}

vector<bool> getCode(Node *n, vector<bool> code) {
    if (n->parent == NULL)
        return code;
    if (n->parent->left == n) {
        code.push_back(0);
    } else {
        code.push_back(1);
    }
    if (n->parent->parent != NULL)
        code = getCode(n->parent, code);
    return code;
}

void outCode(vector<bool> code) {
    for (int i = code.size() - 1; i >= 0; i--) {
        cout << code[i];
    }
}

int main() {
    ifstream file("../test.txt");
    vector<Node *> tree;
    map<char, Node *> leaves;
    Node *root = new Node;
    Node *esc = root;
    tree.push_back(root);

    string word;
    getline(file, word);

    for (auto &letter : word) {
        if (leaves[letter] != NULL) {
            updateWeight(leaves[letter]);

            outCode(getCode(leaves[letter], vector<bool>()));
        } else {
            leaves[letter] = new Node;
            leaves[letter]->code = letter;
            leaves[letter]->parent = esc;

            Node *tmp = new Node;
            tmp->parent = esc;

            esc->left = tmp;
            esc->right = leaves[letter];
            tree.push_back(leaves[letter]);
            tree.push_back(tmp);

            outCode(getCode(esc, vector<bool>()));
            cout << letter;

            esc = tmp;
            updateWeight(leaves[letter]);
        }
        tree = sortTree(tree);
        recount(esc->parent);
    }
    file.close();
    return 0;
}