4. Search with Error
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Write a program to search for a substring in a string. Additional condition: one error is allowed, meaning that one pair of characters may not match.

Input

The first line of the input contains the string $$$s$$$, in which we are searching. The second line contains the substring $$$q$$$, which we are looking for. The strings contain only lowercase Latin letters, and their lengths do not exceed $$$2 \cdot 10^5$$$ characters.

Output

Output a single integer — the position of the occurrence of the substring $$$q$$$ in the string $$$s$$$ (positions are numbered starting from one). If there are multiple correct answers, output the smallest one. If there are no occurrences, output 0.

Example
Input
abacabadaba
bad
Output
2
Note

Solutions that work for strings of length up to 1000 characters can earn up to 40 points.