B. Круг камней
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

По кругу расположено n камней, каждый из которых покрашен в один из 26 цветов (цвета обозначаются строчными буквами латинского алфавита). Цвета некоторых камней могут совпадать.

Круг камней называется пестрым, если любые два соседних камня имеют разные цвета. Два камня в круге считаются соседними, если между ними нет других камней хотя бы в одном направлении. К примеру, первый и второй камни соседние, так же как второй и третий, или последний и первый.

Вам разрешается ровно один раз вынуть из круга любую (возможно пустую) последовательность подряд идущих камней.

Для каждого значения k (0 ≤ k < n) определите, можно ли вынуть ровно k последовательных камней из круга так, чтобы получившийся круг был пестрым.

Входные данные

Входные данные состоят из нескольких тестовых наборов. Каждый тестовый набор состоит из одной строки из n символов, описывающей цвета камней (1 ≤ n ≤ 106). Эта строка состоит из строчных букв латинского алфавита.

Выходные данные

Для каждого тестового набора выведите его номер и строку из n цифр. В этой строке k-я цифра (в 0-индексации) должна быть "1", если можно вынуть из круга k последовательных камней так, чтобы получившийся круг был пестрым. Иначе k-я цифра должна быть "0".

Примеры
Входные данные
rrg
rrrrr
brbg
abab
Выходные данные
Case 1: 011
Case 2: 00001
Case 3: 1111
Case 4: 1011