#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cstring>

using namespace std;
typedef unsigned char byte;

pair<int, int> nodes[3000]; // pair<left son, right son>
int BigToSmall[3000]; // from int to char
char SmallToBig[256]; // from char to int

string code[256];

void Codding(int currentId, string chip = "") {
    //cout << currentId << endl;
    if (BigToSmall[currentId] != -1) {
        code[BigToSmall[currentId]] = chip;
        return;
    }
    Codding(nodes[currentId].first, chip + "0");
    Codding(nodes[currentId].second, chip + "1");
}

void Encode(string text1, string &text2) {
    memset(SmallToBig, -1, sizeof SmallToBig);
    memset(BigToSmall, -1, sizeof BigToSmall);
    byte InputChar = 0;
    vector<int> freqOfChar;
    string originalText = "", compressedText = "";

    freqOfChar.resize(256, 0);
    originalText = text1;
    for (int i = 0; i < originalText.size(); ++i) {
        freqOfChar[originalText[i]]++;
    }

    int countOfNodes = 0;
    vector<pair<int, int>> buffer; // pair<node id, node val>
    for (size_t i = 0; i < 256; ++i) {
        if (freqOfChar[i] != 0) {
            countOfNodes++;
            BigToSmall[countOfNodes] = i;
            SmallToBig[i] = countOfNodes;
            buffer.push_back(make_pair(countOfNodes, freqOfChar[i]));
        }
    }

    while (buffer.size() > 1) {
        sort(buffer.begin(), buffer.end());
        reverse(buffer.begin(), buffer.end());

        pair<int, int> left, right;
        left = buffer.back();
        buffer.pop_back();
        right = buffer.back();
        buffer.pop_back();
        int currentId = ++countOfNodes;

        pair<int, int> newNode = make_pair(currentId, left.second + right.second);

        buffer.push_back(newNode);
        nodes[currentId] = make_pair(left.first, right.first);
    }

    Codding(countOfNodes);

    for (auto currentDiggit : originalText) {
        compressedText = compressedText + code[currentDiggit];
    }
    text2 = compressedText;
}

void Decode(string text1, string &text2) {
    byte InputChar = 0;
    string compressedText = "", originalText = "";

    compressedText = text1;

    string currentCode = "";
    for (size_t i = 0; i < compressedText.size(); ++i) {
        currentCode += compressedText[i];
        for (size_t dig = 0; dig < 256; ++dig) {
            if (code[dig] == currentCode) {
                byte diggit = (byte)dig;
                originalText += diggit;
                currentCode = "";
                break;
            }
        }
    }

    text2 = originalText;
}

int main () {
    string orig, comp, s;
    getline(cin, orig);
    cout << orig << endl;
    Encode(orig, comp);
    cout << comp << endl;
    Decode(comp, s);
    cout << s << endl;
}