#define FAST_ALLOCATOR_MEMORY 1e8
#include <iostream>
#include <fstream>
#include <unordered_map>
#include <vector>
#include <queue>
#include "optimization.h"

using namespace std;

struct Node {
    char data;
    int freq;
    Node *left, *right;
};

Node* add_node(char data, int freq, Node* left, Node* right) {
    Node* node = new Node;
    node->data = data;
    node->freq = freq;
    node->left = left;
    node->right = right;
    return node;
}

auto cmp = [](Node* a, Node* b) {
    return a->freq > b->freq;
};

void encode(Node* root, const string& str, unordered_map<char, string>& codes_map) {
    if (root == nullptr) return;
    if (!root->left && !root->right)
        codes_map[root->data] = str;
    encode(root->left, str + "0", codes_map);
    encode(root->right, str + "1", codes_map);
}

void build(const string& text) {
    unordered_map<char, int> freq;
    for (char data: text)
        freq[data]++;
    priority_queue<Node*, vector<Node*>, decltype(cmp)> q(cmp);
    for (auto pair: freq)
        q.push(add_node(pair.first, pair.second, nullptr, nullptr));
    while (q.size() != 1) {
        Node *left = q.top();
        q.pop();
        Node *right = q.top();
        q.pop();
        int sum = left->freq + right->freq;
        q.push(add_node('\0', sum, left, right));
    }
    Node* root = q.top();
    unordered_map<char, string> codes_map;
    encode(root, "", codes_map);
    string str;
    for (auto data: text) {
        str += codes_map[data];
    }
    cout << codes_map.size() << " " << str.size() << "\n";
    for (const auto& pair: codes_map) {
        cout << pair.first << ": " << pair.second << '\n';
    }
    cout << str << '\n';
}


int main() {
#ifdef LOCAL_DEFINE
    ifstream in("input.txt");
#endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    string text;
    in >> text;
    if (text.size() == 1) {
        cout << 1 << " " << 1 << "\n";
        cout << text << ": 0\n0";
    } else build(text);
    return 0;
}