def decodeHuff(root: Node, s: str) -> None:
    result = []
    curr = root    # start pointer at root node
    for digit in s:
        curr = curr.left if digit == "0" else curr.right
        # if a leaf node is reached, append its character to decoded  
        # string result, and reset pointer back to root of tree
        if not all([curr.left, curr.right]):    # equivalent to `is not None`
            result.append(curr.data)
            curr = root     
    print("".join(result))

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;
    }
}

class Decoding {
    public void decode(String s, Node root) {
        StringBuilder decoded = new StringBuilder();
        Node currentNode = root;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '0') {
                currentNode = currentNode.left;
            } else {
                currentNode = currentNode.right;
            }
            if (currentNode instanceof HuffmanLeaf) {
                decoded.append(currentNode.data);
                currentNode = root;  
            }
        }
        System.out.println(decoded.toString());
    }
}

def decodeHuff(root, s):
    pointer = root
    decode_s = ""
    for c in s:
        if c=="1":
            pointer=pointer.right
        else:
            pointer = pointer.left
        if pointer.data!='\0':
            decode_s += pointer.data
            pointer = root
    print(decode_s)