给定字符串 $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
bbbbbbbOutput 1
0
1
2
3
2
1
0Input 2
acabcaa
babaabcOutput 2
0
2
1
4
1
1
2Scoring
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$。