Heretical Möbius

아직 제출이 없습니다시간 제한1초메모리 제한256 MB

문제

Rikka was walking around the school building curiously until a strange room with a door number of 404 caught her eyes.

It seemed like a computer room --- there were dozens of computers lying orderly, but papers, pens, and whiteboards everywhere built up a nervous atmosphere. Suddenly, Rikka found some mysterious codes displayed on a computer which seemed to have nothing different from others --- is this a message from inner world?

Excited Rikka started her exploration. The message was generated by a program named for_patterns_in_mobius which outputted a string ss of length 10910^9, containing the value of μ(x)\lvert \mu(x) \rvert for x=1,2,,109x = 1, 2, \dots, 10^9 in order.

Suddenly, Rikka heard footsteps outside. She quickly took a screenshot and left. The screenshot recorded a string tt of length 200200, perhaps a substring of ss. Now Rikka wonders if it is really a substring of ss, and if so, where it first appears in ss.

Could you help her to decipher the codes?

입력

There are 1010 lines in total. Each line contains 2020 characters, each of which is either "0" or "1". tt is the concatenation of them --- the result of concatenating them in order.

출력

Output a single integer in the only line. If tt is a substring of ss, output the first position it appears in ss, that is, the minimum positive integer pp such that all the digits μ(p+i)\lvert \mu(p+i) \rvert for i=0,1,,199i = 0, 1, \dots, 199 form the string tt. Otherwise output 1-1.

힌트

The definition of μ()\mu() is as follows: 

For any positive integer xx, let x=_i=1kp_ic_ix = \prod\_{i=1}^k {p\_i}^{c\_i} be the regular factorization of xx, where p_ip\_i is a unique prime, c_ic\_i is a positive integer, and if x=1x=1 then k=0k=0. Consequently, μ(x)\mu(x) is defined as μ(x)={0c_i>1, (1)kotherwise \mu(x)= \begin{cases} 0 & \exists c\_i>1, \\\ (-1)^k & \text{otherwise} \\\ \end{cases}