#include <fstream>
#include <iostream>
using namespace std;

ifstream fin("f.txt");
ofstream fout("g.txt");


void delacc()
{
	fstream file;
	file.open("C:/Users/Артем/Desktop/Шифровка/g.txt", ios::out);
	file << "";
	file.close();
}


struct tree
{
    int elem1;
    char elem2;
    tree *left;
    tree *right;
    tree *lef;
    tree *rig;
};

void fun(int io)
{
    if (io > 0)
    {
        fun(io/10);
        fout << io%10-1;
    }
    return ;
}

void prog(tree *&p, int io)
{
    if (p->rig == NULL)
    {
        fun(io);
        fout << " " << p->elem2 << "\n";
    }
    else
    {
        tree *Le, *Ri;
        Le = p->lef;
        Ri = p->rig;
        io = io*10+1;
        prog(Le, io);
        io++;
        prog(Ri, io);
    }
    return ;
}


int main()
{
    delacc();
    int a, b, c, i, j = 0, swa;
    char q, sw;
    tree *L;
    L = new tree;
    q = fin.get();
    L->elem2 = q;
    L->elem1 = 1;
    L->left = NULL;
    L->right = NULL; L->rig = NULL; L->lef = NULL;
    tree *p, *z;
    while (fin.peek() != EOF)
    {
        q = fin.get();
        p = L;
        while (p->elem2 != q && p->right != NULL)
        {
            p = p->right;
        }
        if (p->elem2 == q) p->elem1++;
        else
        {
            j++;
            z = new tree;
            p->right = z;
            z->left = p;
            p = p->right;
            p->elem2 = q;
            p->elem1 = 1;
            p->right = NULL;
            p->lef = NULL; p->rig = NULL;
        }
    }
    p = L;
    if (p->right != NULL)
    {
        for (i = 1; i <= j; i++)
        {
            p = L;
            while (p->right->right != NULL)
            {
                if (p->elem1 > p->right->elem1)
                {
                    swa = p->elem1;
                    sw = p->elem2;
                    p->elem1 = p->right->elem1;
                    p->elem2 = p->right->elem2;
                    p->right->elem1 = swa;
                    p->right->elem2 = sw;
                }
                p = p->right;
            }
            if (p->elem1 > p->right->elem1)
            {
                swa = p->elem1;
                sw = p->elem2;
                p->elem1 = p->right->elem1;
                p->elem2 = p->right->elem2;
                p->right->elem1 = swa;
                p->right->elem2 = sw;
            }
        }


        while (L->right->right != NULL)
        {
            z = new tree;
            z->elem1 = L->elem1 + L->right->elem1;
            z->lef = L;
            z->rig = L->right;
            z->right = L->right->right;
            z->left = NULL;
            L = z;
            if (z->right != NULL) z->right->left = z;
            while (z->right->elem1 < z->elem1 && z->right->right != NULL)
            {
                if (z->left != NULL)
                {
                    z->left->right = z->right;
                    z->right->left = z->left;
                }
                else
                {
                    z->right->left = NULL;
                    L = z->right;
                }
                z->left = z->right;
                z->right = z->left->right;
                z->right->left = z;
                z->left->right = z;

            }
            if (z->right->elem1 < z->elem1)
            {
                if (z->left != NULL)
                {
                    z->left->right = z->right;
                    z->right->left = z->left;
                }
                else
                {
                    z->right->left = NULL;
                    L = z->right;
                }
                z->left = z->right;
                z->right = z->left->right;
                z->left->right = z;
            }
        }

        z = new tree;
        z->elem1 = L->elem1 + L->right->elem1;
        z->lef = L;
        z->rig = L->right;
        z->right = L->right->right;
        z->left = NULL;
        L = z;
    }

    prog(L, 0);
}