#include <bits/stdc++.h>

using namespace std;

ifstream in("t.in");
ofstream out("t.out");

unordered_map<char, int> M;

struct Node
{
    string simbol;
    int freq;
    Node* left_child;
    Node* right_child;
};

template <class Node> struct greaterr
{
    bool operator()(const Node& first, const Node& second) const
    {
        return first.freq > second.freq;
    }
};

/*void atribuire(Node* nod, string S, int x, Node* lc, Node* rc)
{
    (*nod).simbol = S;
    (*nod).freq = x;
    (*nod).left_child = lc;
    (*nod).right_child = rc;
}*/

vector<pair<string, string>> A;

void Traversal(Node nod, string bins)
{
    bool OK = 0;
    if(nod.left_child)
    {
        OK = 1;
        Traversal(*nod.left_child, bins + "0");
    }
    if(nod.right_child)
    {
        OK = 1;
        Traversal(*nod.right_child, bins + "1");
    }
    if(!OK)
    {
        A.push_back({nod.simbol, bins});
    }
}

int main()
{
    string S;
    getline(in, S);
    for(int i = 0; i < S.size(); ++i)
        M[S[i]]++;
    priority_queue<Node, vector<Node>, greaterr<Node>> Q;
    Node* nod;
    for(auto i : M)
    {
        nod = new Node;
        nod -> simbol = i.first;
        nod -> freq = i.second;
        nod -> left_child = nullptr;
        nod -> right_child = nullptr;
        //atribuire(nod, i.first, i.second, nullptr, nullptr);
        Q.push(*nod);
    }
    Node *left, *right, *father;
    while(Q.size() > 1)
    {
        left = new Node;
        right = new Node;

        left -> simbol = Q.top().simbol;
        left -> freq = Q.top().freq;
        left -> left_child = nullptr;
        left -> right_child = nullptr;
        Q.pop();

        right -> simbol = Q.top().simbol;
        right -> freq = Q.top().freq;
        right -> left_child = nullptr;
        right -> right_child = nullptr;
        Q.pop();

        father = new Node;

        father -> freq = left -> freq + right -> freq;
        father -> simbol = "";
        father -> left_child = left;
        father -> right_child = right;

        Q.push(*father);
    }
    Node Tata = Q.top();
    string bins = "";
    //cout << typeid(Tata).name() << '\n';
    Traversal(Tata, bins);
    for(auto i : A)
    {
        out << i.first << " " << i.second << '\n';
    }
    return 0;
}