"""
задание:
реализовать алгоритм сжатия Хаффмана


Создаю класс дерева, чтобы удобно взаимодействовать и не городить.
Наследую от списка потому что так представляю себе структуру дерева,
сразу определяю сумму элементов и элементы на концах веток дерева.

!!!читая код, имей в виду, что ноды всегда две!!!
"""
class Tree(list):
    def __init__(self, elements, key):
        super().__init__(elements)
        self.sum = 0
        for element in elements:
            if isinstance(element, (int, float)):
                self.sum += key(element)
            elif isinstance(element, Tree):
                self.sum += element.sum
        self.ends = []
        for element in elements:
            if not isinstance(element, Tree):
                self.ends.append(element)


# собственно, тут весь движ
def generate_paths(text):
    # инициализация всего важного:
    # алфавита, кодов знаков (путей на дереве, поэтому и paths)
    # и текущего состояния дерева (изначально просто алфавит, n несвязанных элементов)
    alphabet = sorted(list(set(text)), key=text.count)
    paths = {character: "" for character in alphabet}
    current_tree = Tree(alphabet, key=text.count)  # still sorted
    # во-первых, везде две ноды, так что нужно минимум два элемента
    # во-вторых, мне нужна проверка на полную связность дерева,
    # а если оно полностью связно, то длина списка, его представляющего, равна 1
    while len(current_tree) > 1:
        # присвоение среза не сработало (неявно приводит к списку),
        # так что сделал в 3 строки.
        # дерево (линейное пока что) я отсортировал при инициализации, когда оно еще списком было,
        # так что и беру последние 2 элемента
        two_last = current_tree[-2:]
        current_tree = current_tree[:-2]  # removing last two elements
        current_tree.append(Tree(two_last, key=text.count))
        ### ЗАБАГАННАЯ ОБЛАСТЬ
        # прохожусь по тому, что связал и добавляю в пути новый бит
        for index, element in enumerate(current_tree[-1]):
            # если строка, то добавляю прямо на нее
            if not isinstance(element, Tree):
                paths[element] += str(1-index)
            # если дерево, то прохожусь по концам веток и делаю то же самое
            else:
                for end in element.ends:
                    paths[end] += str(1-index)
        ### ЗАБАГАННАЯ ОБЛАСТЬ
        # наконец, в конце итерации сортирую по количеству опять
        current_tree.sort(key = lambda x: text.count(x) if isinstance(x, str)
                                                        else x.sum)
    return paths
# изначально нужно было сортировать по вероятности пока она не станет 1,
# но это эквивалентно, ведь количество вхождений пропорционально вероятности,
# а при вероятности 1 дерево будет связным


if __name__ == "__main__":
    from pprint import pprint
    text = input()
    pprint(generate_paths(text))

# анекдот: Буротино утонул, а там русалка на шпагат села