#include <bits/stdc++.h>

using namespace std;

int main() {
    string s;
    getline(cin, s);
    map<string, int> count;
    for (auto i : s)
        count[string(1, i)]++;

    set<pair<int, string>> st;
    for (auto &[_string, _int] : count) {
        st.insert({_int, _string});
    }
    map<char, string> code;
    for (int i = 0; i < count.size() - 1; ++i) {
        auto [cnt1, letters1] = *st.begin();
        st.erase(st.begin());
        auto [cnt2, letters2] = *st.begin();
        st.erase(st.begin());
        for (auto c : letters1) {
            code[c] = "0" + code[c];
        }
        for (auto c : letters2) {
            code[c] = "1" + code[c];
        }
        st.insert({cnt1 + cnt2, letters1 + letters2});
    }
    for (auto& [c, s] : code) {
        cout << c << " " << s << "\n";
    }
}