题目描述

$\huge\texttt{FAT}$ 想要烫串串。

现在有一个长度为 $n$ 的字符串 $S$ 与一个长度为 $m$ 的字符串 $T$

定义字符串 $S_i$ 表示将从 $S$ 的第 $i$ 个字符后断开得到前缀 $A$，$B$，将 $B$ 从尾到头形成的字符串设为 $B'$，将 $B'$ 接在 $A$ 后面得到的字符串。

对于每个 $i$，$\huge\texttt{FAT}$ 想知道 $T$ 在 $S_i$ 中出现的次数。

输入格式

第一行包含一个字符串 $S$。

第二行包含一个字符串 $T$。

输出格式

输出 $n$ 行每行一个整数，第 $i$ 行的数表示 $T$ 在 $S_i$ 中出现的次数。

样例

样例输入

abaa
aa

样例输出

2
1
1
1

样例解释

$S_1=\texttt{aaab}$

$S_2=\texttt{abaa}$

$S_3=\texttt{abaa}$

$S_4=\texttt{abaa}$

数据范围

对于前 $20\%$ 的数据，$1\le m \le n\le 10^3$。

对于 $100\%$ 的数据，$1\le m \le n\le 2\times 10^6$。