Welcome to ZOJ
 Problem Sets Information Select Problem Runs Ranklist
ZOJ Problem Set - 4010
Neighboring Characters

Time Limit: 4 Seconds      Memory Limit: 65536 KB

Given a string $s$ of length $n$, let's define the neighbors of the $i$-th character ($1 \le i \le n$) as follows:

• If $1 < i < n$, the neighbors of the $i$-th character are the $(i-1)$-th character and the $(i+1)$-th character;
• If $i = 1$, the neighbors of the 1st character are the 2nd character and the $n$-th character;
• If $i = n$, the neighbors of the $n$-th character are the $(n-1)$-th character and the 1st character.

A string $s$ is good, if and only if all the characters in the string are different from their neighbors.

DreamGrid would like to delete $k$ continuous characters from string $s$ to form a new string $\bar{s}_k$. Note that the $n$-th character and the 1st character are also continuous (you can consider the string as a ring). Please tell him if it's possible to make $\bar{s}_k$ a good string for all $0 \le k < n$.

#### Input

There are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:

The first and only line contains a string $s$ ($1 \le |s| \le 10^6$) consists of lowercase English letters.

It's guaranteed that the sum of $|s|$ over all test cases will not exceed $1.2 \times 10^7$.

#### Output

For each test case output one line containing one string of length $|s|$ consists of '0' and '1'. If the $i$-th (the index starts from 1) character is '1', it is possible to make $\bar{s}_{i-1}$ a good string; If its '0', it is impossible to make $\bar{s}_{i-1}$ a good string.

#### Sample Input

5
abab
aabbaa
abcabc
abcdef
a


#### Sample Output

1011
000011
110111
111111
1


#### Hint

For the first sample test case:

• When $k = 0$, string "abab" is good;
• When $k = 2$, string "ab" is good;
• When $k = 3$, string "a" is good.

Author: CHEN, Jingbang
Source: ZOJ Monthly, March 2018
Submit    Status