#include <bits/stdc++.h>
using namespace std;

struct Node {
    char ch;               // 对于非叶节点，ch = 0
    int freq;
    bool isLeaf;
    int firstPos;          // 在文本中首次出现的位置（用于 tie-break）
    Node *left, *right;
    int createOrder;       // 创建顺序编号，用于非单节点比较

    Node(char c, int f, int pos, int order)
        : ch(c), freq(f), isLeaf(true), firstPos(pos),
          left(NULL), right(NULL), createOrder(order) {}

    Node(Node* l, Node* r, int f, int order)
        : ch(0), freq(f), isLeaf(false), firstPos(INT_MAX),
          left(l), right(r), createOrder(order) {}
};

/*
   优先队列排序规则：
   1. 权值小的优先
   2. 权值相等时：
      a. 单节点优先于非单节点
      b. 若均为单节点 → 按 firstPos 小的优先
      c. 若均为非单节点 → 按 createOrder 小的优先
*/
struct Cmp {
    bool operator()(Node* a, Node* b) {
        if (a->freq != b->freq) return a->freq > b->freq;

        // freq 相同
        if (a->isLeaf != b->isLeaf) return a->isLeaf < b->isLeaf;

        if (a->isLeaf) return a->firstPos > b->firstPos;
        return a->createOrder > b->createOrder;
    }
};

unordered_map<char, string> codeMap;

// 生成哈夫曼编码
void dfs(Node* root, string path) {
    if (!root) return;
    if (root->isLeaf) {
        codeMap[root->ch] = path;
        return;
    }
    dfs(root->left, path + "0");
    dfs(root->right, path + "1");
}

// 用哈夫曼树译码二进制串
string decode(Node* root, const string& s) {
    string result;
    Node* cur = root;
    for (char c : s) {
        if (c == '0') cur = cur->left;
        else if (c == '1') cur = cur->right;
        else return "INVALID";

        if (!cur) return "INVALID";
        if (cur->isLeaf) {
            result.push_back(cur->ch);
            cur = root;
        }
    }
    if (cur != root) return "INVALID"; // 未在叶节点结束
    return result;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    string text, code1, code2;
    cin >> text >> code1 >> code2;

    // 统计出现次数 & 首次出现位置
    unordered_map<char, int> freq, firstPos;
    for (int i = 0; i < text.size(); i++) {
        char c = text[i];
        freq[c]++;
        if (!firstPos.count(c)) firstPos[c] = i;
    }

    // 创建优先队列
    priority_queue<Node*, vector<Node*>, Cmp> pq;
    int createId = 0;

    for (auto& p : freq) {
        char c = p.first;
        int f = p.second;
        pq.push(new Node(c, f, firstPos[c], createId++));
    }

    // 构建唯一哈夫曼树
    while (pq.size() > 1) {
        Node* a = pq.top(); pq.pop();
        Node* b = pq.top(); pq.pop();
        Node* parent = new Node(a, b, a->freq + b->freq, createId++);
        pq.push(parent);
    }

    Node* root = pq.top();

    // 生成编码
    dfs(root, "");

    // 计算压缩前后大小
    int originalBytes = text.size();
    long long bits = 0;
    for (char c : text) bits += codeMap[c].size();
    long long compressedBytes = (bits + 7) / 8;

    cout << originalBytes << " " << compressedBytes << "\n";

    // 按题目要求排序输出编码（按频率升序，同频率按出现顺序）
    vector<tuple<int,int,char>> order;
    for (auto& p : freq) {
        order.emplace_back(p.second, firstPos[p.first], p.first);
    }
    sort(order.begin(), order.end());

    for (auto& t : order) {
        char c = get<2>(t);
        cout << c << ":" << codeMap[c] << "\n";
    }

    // 译码
    string out1 = decode(root, code1);
    string out2 = decode(root, code2);

    cout << out1 << "\n";
    cout << out2 << "\n";

    return 0;
}