边界

给定一个字符串 $S$，定义如下：

• $|S|$ 表示字符串 $S$ 的长度；
• $S[l:r]$ 表示字符串 $S$ 的第 $l$ 个到第 $r$ 个字符按顺序拼接形成的子串，其中 $1 \le l \le r \le |S|$；
• 若存在整数 $b$ 满足 $1 \le b < |S|$，且

$$S[1:b]=S[|S|-b+1:|S|],$$

则称 $b$ 是字符串 $S$ 的一个 border 长度。

现在给定两个长度相同的非空字符串 $S,T$。

对于每个 $1 \le i \le |S|$，独立进行如下询问：

• 将 $S$ 的第 $i$ 个字符替换为 $T$ 的第 $i$ 个字符，得到新字符串 $S'$；
• 求字符串 $S'$ 的最大 border 长度。

如果 $S'$ 不存在 border，则输出 $0$。

注意，所有询问互相独立，也就是说每次询问都基于原串 $S$ 进行替换，不会受到其他询问的影响。

输入格式

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

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

保证 $|S|=|T|$。

输出格式

输出 $|S|$ 行。

第 $i$ 行输出一个整数，表示将 $S$ 的第 $i$ 个字符替换为 $T$ 的第 $i$ 个字符后得到的新字符串的最大 border 长度。

样例 1

输入

aaaaaaa
bbbbbbb

输出

0
1
2
3
2
1
0

样例 2

输入

acabcaa
babaabc

输出

0
2
1
4
1
1
2

提示

本题共 $20$ 组数据。

对于前 $10\%$ 的数据，$|S| \le 50$。

对于前 $30\%$ 的数据，$|S| \le 5000$。

对于前 $60\%$ 的数据，$|S| \le 10^5$。

对于 $100\%$ 的数据，$1 \le |S|=|T| \le 2 \times 10^6$，且 $S,T$ 仅由小写字母组成。