题目描述

小红有一个长度为n的字符串s，由0、1和 * 组成，可以把*替换成0或者1，小红想知道替换后的字符串的最短周期是多少。如果一个字符串每一个位置的字母都与后k位的字母相同，那么k即为该字符串的一个周期。形式化的说，如果存在一个正整数k 使得对于所有的 i属于[1,n - k] 都有 s[i]= s[i+k] ，那么称k是字符串s的周期。

输入描述

第一行输入一个长度为n(1 <= n <= 1e3)，且只由0、1和*组成的字符串s。

输出描述

输出包含两行，第一行是最短的周期k，

第二行是字符串的周期。如果周期里面包含*，直接输出即可。例如："1010*"，最短周期是3，周期是"10*"。如果周期能确定，则输出确定的周期。

输入示例

1*011*0*1

输出示例

4
1*01

提示信息

替换为1011011拥有最短周期。由于*可以随意变换，所以这里换不换不影响周期的大小。

时间限制：c/c++：1s；java：6s；其他语言：3s。