[POI2011]OKR-Periodicity

题意翻译

给定一个字符串S,其长度为N,如果对于任意的i(1<=i<=n-t)有Si=Si+t(1<=t

题目描述

Byteasar, the king of Bitotia, has ordained a reform of his subjects' names. The names of Bitotians often contain repeating phrases, e.g., the name Abiabuabiab has two occurrences of the phrase abiab. Byteasar intends to change the names of his subjects to sequences of bits matching the lengths of their original names. Also, he would very much like to reflect the original repetitions in the new names. In the following, for simplicity, we will identify the upper- and lower-case letters in the names. For any sequence of characters (letters or bits) ![](http://main.edu.pl/images/OI18/okr-en-tex.1.png) we say that the integer ![](http://main.edu.pl/images/OI18/okr-en-tex.2.png) (![](http://main.edu.pl/images/OI18/okr-en-tex.3.png)) is a period of ![](http://main.edu.pl/images/OI18/okr-en-tex.4.png) if ![](http://main.edu.pl/images/OI18/okr-en-tex.5.png) for all ![](http://main.edu.pl/images/OI18/okr-en-tex.6.png). We denote the set of all periods of ![](http://main.edu.pl/images/OI18/okr-en-tex.7.png) by ![](http://main.edu.pl/images/OI18/okr-en-tex.8.png). For example, ![](http://main.edu.pl/images/OI18/okr-en-tex.9.png), ![](http://main.edu.pl/images/OI18/okr-en-tex.10.png), and ![](http://main.edu.pl/images/OI18/okr-en-tex.11.png). Byteasar has decided that every name is to be changed to a sequence of bits that: has length matching that of the original name, has the same set of periods as the original name, is the smallest (lexicographically1) sequence of bits satisfying the previous conditions. For example, the name ABIABUABIAB should be changed to 01001101001, BABBAB to 010010, and BABURBAB to 01000010. Byteasar has asked you to write a program that would facilitate the translation of his subjects' current names into new ones. If you succeed, you may keep your current name as a reward!

输入输出格式

输入格式


In the first line of the standard input there is a single integer ![](http://main.edu.pl/images/OI18/okr-en-tex.12.png) - the number of names to be translated (![](http://main.edu.pl/images/OI18/okr-en-tex.13.png)). The names are given in the following lines, one in each line. Each name consists of no less than ![](http://main.edu.pl/images/OI18/okr-en-tex.14.png) and no more than ![](http://main.edu.pl/images/OI18/okr-en-tex.15.png) upper-case (capital) letters (of the English alphabet). In the test worth 30% of the points each name consists of at most ![](http://main.edu.pl/images/OI18/okr-en-tex.16.png) letters.

输出格式


Your program should print ![](http://main.edu.pl/images/OI18/okr-en-tex.17.png) lines to the standard output. Each successive line should hold a sequence of zeroes and ones (without spaces in between) corresponding to the names given on the input. If an appropriate sequence of bits does not exists for some names, then "XXX" (without quotation marks) should be printed for that name.

输入输出样例

输入样例 #1

3
ABIABUABIAB
BABBAB
BABURBAB

输出样例 #1

01001101001
010010
01000010

说明