全对!
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 1024 M,其他语言2048 M
64bit IO Format: %lld

题目描述

\hspace{15pt}🤓✋哦对的对的,🤨哦不对,😫啊我跟你们说不对,哎呀不对,🤔哦对的对的对的对…对吗?
\hspace{15pt}哦对的对的对的😁,😐😨不对吧,啊我都搞晕掉了😵💫哦😲对对对对对,对对对对我明白了
\hspace{15pt}小 S 有 n 个对错机器人,每个对错机器人的行为逻辑由一个长度不超过 16,仅由字符 \texttt{`0'}\texttt{`1'} 构成的字符串表示。在本题中,我们记字符串的下标从 1 开始。
\hspace{15pt}对于第 i 个机器人,记其初始字符串为 s_i,其会先将这个字符串无限重复拼接成一个无限长的循环字符串 s_i^{\infty}。随后,对于第 j 时刻,它会根据 s_i^{\infty} 的第 j 个字符来决定回答「对的」还是「不对」:
\hspace{23pt}\bullet\,如果 s_i^{\infty} 的第 j 个字符为 \texttt{`1'},则表示第 i 个机器人在第 j 秒回答「对的」;
\hspace{23pt}\bullet\,如果 s_i^{\infty} 的第 j 个字符为 \texttt{`0'},则表示第 i 个机器人在第 j 秒回答「不对」。
\hspace{15pt}更具体地,如果某个机器人的初始字符串是 \texttt{ ,那么这个机器人会在第 1,3,5,6,8,10,11,\dots 秒回答「对的」,在第 2,4,7,9,12,\dots 秒回答「不对」。

\hspace{15pt}请问是否存在一个时刻 t,使得所有机器人在第 t 秒都回答「对的」,这样的时刻被称为「全对时刻」。如果存在,输出最小的「全对时刻」;否则,输出 -1

输入描述:

\hspace{15pt}第一行输入一个整数 n\left(1 \leq n \leq 10^5\right),表示对错机器人的数量。
\hspace{15pt}此后 n 行,第 i 行输入一个长度为 1 \leq |s_i| \leq 16,仅由字符 \texttt{`0'}\texttt{`1'} 构成的字符串 s_i,表示第 i 个机器人的初始字符串。

输出描述:

\hspace{15pt}输出一个整数 t,表示使得所有机器人在第 t 秒都回答「对的」的最小时刻;如果不存在这样的时刻,输出 -1
示例1

输入

复制
3
001
0110
10001

输出

复制
6

说明

\hspace{15pt}在这个样例中:
\hspace{23pt}\bullet\,1 个机器人的循环字符串为 \texttt{
\hspace{23pt}\bullet\,2 个机器人的循环字符串为 \texttt{
\hspace{23pt}\bullet\,3 个机器人的循环字符串为 \texttt{
\hspace{15pt}观察可知,在秒数 t = 6 时,三者的第 6 个字符均为 \texttt{1},因此输出 6
示例2

输入

复制
2
10
01

输出

复制
-1