Dreamoon 有一个字符串 s 和一个模式字符串 p。他首先从 s 中删除 x 个字符,得到字符串 s' 作为结果。然后他计算$$\mathsf{occ}(s',p)$$,它被定义为可以在s'中找到的等于p的非重叠子串的最大数量。他想让这个数字尽可能大。
更正式地说,让我们将 $$\operatorname{ans}(x)$$ 定义为 $$\mathsf{occ}(s',p)$$ 在所有 s' 上的最大值,该最大值可以通过从 s 中精确删除 x 个字符来获得。 Dreamoon 想知道 $$\operatorname{ans}(x)$$ 对于从 0 到 |s| 的所有 x其中|s|表示字符串 s 的长度。
输入
输入的第一行包含字符串 s (1 ≤ |s| ≤ 2 000)。
输入的第二行包含字符串 p (1 ≤ |p| ≤ 500)。
两个字符串都仅包含小写英文字母。
输出
打印 |s| + 单行中的 1 个空格分隔的整数,表示从 0 到 |s| 的所有 x 的 $$\operatorname{ans}(x)$$。
示例
输入 #1
aaaaa aa
输出 #1
2 2 1 1 0 0
输入 #2
axbaxxb ab
输出 #2
0 1 1 2 1 1 0 0
注意
对于第一个样本,去除 0 到 |s| 后 s' 对应的最佳值= s 中的 5 个字符是 {"aaaaa", "aaaa", "aaa", "aa", "a", ""}。
对于第二个样本,s'可能对应的最佳值为{“axbaxxb”,“abaxxb”,“axbab”,“abab”,“aba”,“ab”,“a”,“”}。