Infinite String Search

Time limit: 2000 msMemory limit: 256 MB

You are given a string $S$ , and a pattern $P$ .

Define the sequence $S_0, S_1, S_2, \dots$ as follows:

\begin{align*} S_0 & = S \\ S_{n + 1} & = S_n + \operatorname{flip}(S_n) \end{align*}

where we define $\operatorname{flip}(T) = \texttt{the string obtained by flipping every bit of } T \texttt{ from 1 to 0 and 0 to 1}$ .

For example, if $S = \texttt{01}$ , we obtain the sequence

S_0 = \texttt{01} \\ S_1 = \texttt{0110} \\ S_2 = \texttt{01101001} \\ \vdots

If we assume the sequence goes on forever, we obtain an infinite string. Your task is to find the first position where the pattern $P$ appears in this infinite string generated from $S$ .

Input

The first line of input contains the string $S$ ( $1 \le |S| \le 10^6$ ).

The second line of input contains the pattern $P$ ( $1$ ).

Output

Output a single integer $i$ , the 0-based index of the first position where the pattern $P$ appears in the generated string. If the pattern never appears in the string, output $-1$ .

Samples

Sample 1

Input

01
00

Output

The first few characters of the generated string are: $\texttt{01101\underline{00}1}\dots$

The pattern occurs at position 5.

Sample 2

Input

01
000

Output

-1

It's possible to prove that the pattern $\texttt{000}$ never occurs in the generated string.

Sample 3

Input

101101011
10111

Output

Infinite String Search

Input

Output

Samples

Sample 1

Sample 2

Sample 3

Submit

Submissions