题目描述

桌子上有 $n$ 个石头围成一个环。每个石头都有一种颜色。每种颜色可以用不同的小写英文字母表示，所以总共有$26$种颜色。不同的石头可能有相同的颜色。如果每一对相邻的石头都是不同颜色的，则称这$n$个石头构成的环是美丽的。两个石头是相邻的充要条件是这两个石头中间没有其他石头。例如：$1$号和 $2$号是相邻的，$2$号和$3$号是相邻的，…，$n$号和$1$号是相邻的。现在，你可以从这 $n$ 个石头中拿走一段连续的石头（可以为空），且你只能拿一次。你的任务是对于每个$k(0≤k≤n-1)$，判断是否存在一种取石头的方案，使得在拿走$k$个连续的石头后，剩下的$n-k$个石头构成的环是美丽的。

输入

输入包含多组测试数据，以$EOF$结束。 每组数据有一行字符串$s$，字符串第$i$位表示桌上第$i$个石头的颜色。设字符串$s$的长度为$n$，则$1≤n≤10^6$。字符串只包含小写英文字母。

输出

对于每组数据，按照样例的格式输出数据编号和一个长度为$n$的字符串。如果存在一种取石头的方案，使得在拿走$k$个连续的石头后，剩下的$n-k$个石头构成的环是美丽的，则字符串的第$k$位（由$0$开始编号）为$1$，否则为$0$。

输入样例

rrg
rrrrr
brbg
abab

输出样例

Case 1: 011
Case 2: 00001
Case 3: 1111
Case 4: 1011

提示

【数据规模】 对于所有数据，数据组数不超过 $6$ 组，$1≤n≤10^6$。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共8个测试点，非原站或官方原始数据。总分100分。