题目描述

给定一个长度为 $n$ 的字符串 $s$ 和一个长度为 $m$ 的字符串 $c$ ，定义等级$\text{level}$$(s_i,c)$表示字符串 $s$ 中最多有多少个字符串 $c$，注意要互不重叠 。

现在你可以在任意位置删除任意个字符。

你需要算出在删除 $i (0 \le i \le n)$个字符后得到的字符串$s_i$的$\text{level}$$(s_i,c)$。

格式

输入格式

第一行是字符串$s$。

第二行是字符串$c$。

输出格式

输出$(n+1)$个数，第 $i$ 个数表示删除 $i-1$ 个字符后得到的字符串$s_{i-1}$的$\text{level}$$(s_i,c)$。

样例1

样例输入1

axbaxxb
ab

样例输出1

0 1 1 2 1 1 0 0

限制

$100\%$的数据：$n \le 2000, m \le 500$。