题目描述

给定一个长度为 \(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\)。