#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <utility>
#include <memory>
#include <algorithm>

using std::string;
using std::cout;
using std::cin;
using std::endl;
using std::cerr;
using std::vector;
using std::map;
using std::shared_ptr;

struct Huffman_Node;

using Huffman_Node_ptr = shared_ptr<Huffman_Node>;
using Haffman_pair_of_ptr = std::pair<Huffman_Node_ptr, Huffman_Node_ptr>;

struct Huffman_Node {
    Haffman_pair_of_ptr pair;
    int count;
    char char_of_node;

    bool isLeaf() const {
        return pair.first == nullptr &&
            pair.second == nullptr;
    }
};

bool operator<(const Huffman_Node& left, const Huffman_Node& right) {
    return left.count < right.count;
}

bool Huffman_compression(vector<Huffman_Node>& vec) {
    int size_ = vec.size();
    if (size_ <= 1) return false;
    std::sort(vec.rbegin(), vec.rend());
    Huffman_Node new_node{
        Haffman_pair_of_ptr(std::make_shared<Huffman_Node>(vec[size_ - 1]),
    std::make_shared<Huffman_Node>(vec[size_ - 2])),
    vec[size_ - 1].count + vec[size_ - 2].count,
    0
    };
    vec.pop_back();
    vec.pop_back();
    vec.push_back(std::move(new_node));
    return true;
}

void Huffman_node_dfs_to_map(const Huffman_Node& node, string code_of_node, map<char, string>& Huffman_map) {
    if (!node.isLeaf()) {
        Huffman_node_dfs_to_map(*(node.pair.first), code_of_node + '1', Huffman_map);
        Huffman_node_dfs_to_map(*(node.pair.second), code_of_node + '0', Huffman_map);
    }
    else {
        Huffman_map[node.char_of_node] = code_of_node;
    }
}


int main() {
    string str;
    vector<int> count_of_char(26, 0);
    std::cin >> str;
    for (auto& c : str) {
        ++count_of_char[c - 'a'];
    }
    vector<Huffman_Node> Huffman_Nodes;
    for (int i = 0; i != 26; ++i) {
        if (int count = count_of_char[i]) {
            Huffman_Node node{
                Haffman_pair_of_ptr(nullptr,nullptr),
                count,
                static_cast<char>(i + 'a')
            };
            Huffman_Nodes.push_back(std::move(node));
        }
    }
    while (Huffman_compression(Huffman_Nodes)) {}

    map<char, string> Huffman_map;
    Huffman_node_dfs_to_map(Huffman_Nodes[0], "", Huffman_map);

    if (Huffman_map.size() == 1) {
        Huffman_map.begin()->second = "0";
    }

    string code;
    for (auto& c : str) {
        code += Huffman_map[c];
    }

    cout << Huffman_map.size() << ' ' << code.size() << endl;

    for (auto& s : Huffman_map) {
        cout << s.first << ": " << s.second << endl;
    }
    cout << code;

    return 0;
}