Find the Substring

Find the first occurrence of the pattern in the text, where * stands for exactly one arbitrary character rather than a string of any length. Return −1 if there is none; indices start from 0.

输入格式

Two lines s and p. In the original, the text s is a..z, and the pattern p is a..z with at most one *; the original has no length bound, and this site uses 0≤length of each string≤200000. An empty pattern matches at 0.

输出格式

Output a single integer answer.

样例 1

输入：

abcabc
a*c

输出：

0

样例 2

输入：

aaaa
*b

输出：

-1

样例 3

输入：

abc

输出：

0

样例说明

The outputs of the three public examples are, in order: 0; -1; 0. Checked by independent enumeration or direct simulation.