Find the Pattern

Hard#strings #kmp #string-matching· solved by 0 · time limit 2.0 s

Print the 0-based index of the first occurrence of pattern $p$ in text $t$ , or -1. For long inputs a naive search may be too slow in worst cases — try the KMP algorithm.

Input

Line 1: text $t$ . Line 2: pattern $p$ .

Output

The index or -1.

Constraints

$1 \le |p| \le |t| \le 2 \times 10^5$ , lowercase letters.

Sample 1

Input

hello
ll

Output

Sample 2

Input

aaaaa
bba

Output

-1