Given a string $S$, we have the following definitions:

• $|S|$ is the length of string $S$.
• $S[l:r]$ is the substring formed by concatenating the $l$-th to $r$-th characters of $S$ ($1 \le l \le r \le |S|$).
• $b$ is the length of a border if and only if $1 \le b < |S|$ and $S[1:b] = S[|S|-b+1:|S|]$.

Given two non-empty strings $S$ and $T$ of the same length, for every $1 \le i \le |S|$, answer the following query:

• Suppose we replace the $i$-th character of $S$ with the $i$-th character of $T$ to form a new string $S'$. What is the length of the maximum (longest) border of $S'$? If no border exists, return $0$.

Note that different queries are independent, meaning they do not affect each other.

Input

The first line contains a string $S$ consisting only of lowercase letters.

The second line contains a string $T$ consisting only of lowercase letters.

Output

$|S|$ lines, each containing an integer. The integer on the $i$-th line represents the length of the maximum border of the new string $S'$ formed by replacing the $i$-th character of $S$ with the $i$-th character of $T$.

Examples

Input 1

aaaaaaa
bbbbbbb

Output 1

0
1
2
3
2
1
0

Input 2

acabcaa
babaabc

Output 2

0
2
1
4
1
1
2

Subtasks

Subtask $1$ ($23\%$): $|S| \le 50$.

Subtask $2$ ($31\%$): $|S| \le 5000$.

Subtask $3$ ($37\%$): $|S| \le 1 \times 10^5$.

Subtask $4$ ($9\%$): $|S| \le 2 \times 10^6$.