给定字符串 $S$, 我们可以有如下的定义：

• $|S|$ 为字符串 $S$ 的长度。
• $S[l:r]$ 为字符串 $S$ 的第 $l$ 至 $r$ 个字符顺次拼接形成的子串($1 \le l \le r \le |S|$)。
• 为其 border 长度当且仅当 $1 \le b < |S|$，且 $S[1:b]=S[|S|-b+1:|S|]$。

给定长度相同的非空字符串 $S,T$，对于任意 $1 \le i \le |S|$, 进行如下询问：

• 假设将 $S$ 的第 $i$ 个字符替换为 $T$ 的第 $i$ 个字符，形成的新字符串 $S'$ 的最大(最长)的 border 是多少。如果不存在 border, 则返回 $0$。

注意不同的询问之间互相独立，也就是不同的询问之间不会互相影响。

Input

第一行一个仅由小写字符组成的字符串 $S$。

第二行一个仅由小写字符组成的字符串 $T$。

Output

$|S|$ 行, 每行一个整数。第 $i$ 行的整数表示 $S$ 的第 $i$ 个字符替换为 $T$ 的第 $i$ 个字符，形成的新字符串 $S'$ 的最大的 border。

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

Scoring

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$。