Escape Sequences

Time limit1sMemory limit512 MB

Summary

For a morphism f that replaces a with aa and b with ab, find the smallest k such that t is a substring of the k-fold iterate f^k(s).

Level: Hard8 of 10
Topics: String, Divide and conquer, Math, Binary search
Solved: No attempts yet

Problem

For a string $s$ consisting of only 'a' and 'b', let $f(s)$ be the string obtained by replacing every 'a' in $s$ with 'aa' and every 'b' with 'ab'. For example, $f($ "aba" $) =$ "aaabaa"$.

Given strings $s$ and $t$ , find the smallest non-negative integer $k$ such that $t$ is a contiguous substring of $f^k(s)$ .

$f^k$ is defined as follows.

$f^0(s) = s$
$f^k(s) = f^{k - 1}(f(s))$

Input

The first line and the second line contain string $s$ and string $t$ respectively ( $1 \leq |s|, |t| \leq 2 \cdot 10^5$ ).

Strings $s$ and $t$ consist of only the characters 'a' and 'b'.

Output

Print a single integer, the minimum $k$ .

If $k$ does not exist, print "-1" instead.

Examples3

Example 1
Input
```
b
ab
```
Expected output
```
1
```
Example 2
Input
```
ababa
bab
```
Expected output
```
0
```
Example 3
Input
```
a
b
```
Expected output
```
-1
```