function main() {
    const ws: WriteStream = createWriteStream(process.env['OUTPUT_PATH']);
    const s: string = readLine().trim()

    let [code, tree] = Tree.encode(s)
    // ws.write(code + '\n');
    ws.write(Tree.decode(code, tree) + '\n');
}


// # classes
class Node {
    value: string
    freq: number
    left: Node | null
    right: Node | null
    constructor(value: string, freq: number) {
        this.value = value, this.freq = freq, this.left = null, this.right = null
    }
}
class Tree {
    root: Node | null
    constructor() { this.root = null }
    static fromStr(input: string): Tree {
        const freq: { [char: string]: number } = {};
        for (const char of input) { if (!freq[char]) { freq[char] = 0; } freq[char]++; }

        const tree = new Tree();
        const nodes: Node[] = [];
        for (const char in freq) { nodes.push(new Node(char, freq[char])); }

        while (nodes.length > 1) {
            nodes.sort((a, b) => a.freq - b.freq);
            const left = nodes.shift()!;
            const right = nodes.shift()!;
            const newNode = new Node('', left.freq + right.freq);
            newNode.left = left;
            newNode.right = right;
            nodes.push(newNode);
        }

        tree.root = nodes[0]
        return tree
    }
    private order(node: Node | null, code: string, values: [string, string][]): void {
        if (!node) return;
        if (node.value !== '') values.push([node.value, code])
        this.order(node.left, code + '0', values);
        this.order(node.right, code + '1', values);
    }
    public get_order() {
        let values: [string, string][] = []
        this.order(this.root, '', values)
        return values
    }

    static encode(s: string): [string, Tree] {
        let tree = Tree.fromStr(s)
        let orde = tree.get_order()
        let hash = s.split('').map(c => [c, orde.find(e => e[0] == c)[1]])
        let resu = hash.map(([char, code]) => code).join('')

        console.log(hash.map(([char, code]) => char.padEnd(code.length, ' ')).join(' '))
        console.log(hash.map(([char, code]) => code).join(' '))
        console.log('or')
        console.log(resu)

        return [resu, tree];
    }
    static decode(code: string, tree: Tree): string {
        let s = '';
        let node = tree.root;

        for (const bit of code) {
            if (node == null) return s;
            if (bit === '0') { node = node.left; }
            else { node = node.right; }

            if (node && node.value !== '') {
                s += node.value; node = tree.root;
            }
        }
        return s;
    }
}