400395: GYM100162 B Circle of Stones

Memory Limit:256 MB Time Limit:3 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

B. Circle of Stonestime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

There are n stones on the table in a circle, each of them has a color. Colors are represented by lowercase English letters, so there are 26 possible colors. Different stones can have equal colors.

The circle of stones is called motley if every two neighboring stones have different colors. Stones in a circle are considered neighboring if there are no other stones between them in at least one direction. For example, the 1st and the 2nd stones are neighboring, as well as the 2nd and the 3rd, or the n-th and the 1st.

You are allowed to take away any (possibly empty) sequence of consecutive stones. And you can do this operation only once.

Determine for each k (0 ≤ k < n) if it is possible to take away k stones so that the resulting circle would be motley.

Input

The input contains several test cases. Each test case is a single line, which is a description of n stones lying on the table (1 ≤ n ≤ 106). This line contains only lowercase English letters.

Output

For each test case, display the case number and a string of n digits. The k-th digit (0-indexed) must be "1" if it is possible to take away a segment of k consecutive stones so that the resulting circle would be motley. Otherwise the k-th digit must be "0".

ExamplesInput
rrg
rrrrr
brbg
abab
Output
Case 1: 011
Case 2: 00001
Case 3: 1111
Case 4: 1011

加入题单

上一题 下一题 算法标签: