寒假马上就要到了。查内克先生想用装饰品装饰他房子的墙壁。墙可以表示为长度为 $$$n$$$ 的二进制字符串 $$$a$$$。他最喜欢的侄子有另一个长度为 $$$m$$$ 的二进制字符串 $$$b$$$ ($$$m \leq n$$$)。
Chanek 先生的侄子喜欢非负整数 $$$k$$$。他的侄子想要 $$$k$$$ 出现 $$$b$$$ 作为 $$$a$$$ 中的子字符串。
然而,Chanek 先生不知道 $$$k$$$ 的价值。因此,对于每个 $$$k$$$ ($$$0 \leq k \leq n - m + 1$$$),找到 $$$a$$$ 中必须更改的最小元素数,使得 $$$a$$$ 中 $$$b$$$ 恰好出现 $$$k$$$ 次。
如果存在 $$$k$$$ 个不同的对 $$$(p,q)$$$,则字符串 $$$s$$$ 在 $$$t$$$ 中恰好出现 $$$k$$$ 次,这样我们可以通过删除 $$$t$$$ 开头的 $$$p$$$ 字符和删除 $$$t$$$ 结尾的 $$$q$$$ 字符来获得 $$$s$$$。
输入
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq m \leq n \leq 500$$$) — 分别是二进制字符串 $$$a$$$ 和 $$$b$$$ 的大小。
第二行包含长度为 $$$n$$$ 的二进制字符串 $$$a$$$。
第三行包含长度为$$$m$$$的二进制字符串$$$b$$$。
输出
输出 $$$n - m + 2$$$ 整数 — 第 $$$(k+1)$$$ 个整数表示 $$$a$$$ 中必须更改的最小元素数,因此 $$$b$$$ 作为子字符串在 $$$a$$$ 中恰好出现 $$$k$$$ 次。
示例
输入 #1
9 3 100101011 101
输出 #1
1 1 0 1 6 -1 -1 -1
注意
对于$$$k = 0$$$,要使字符串$$$a$$$中不出现101,可以按如下方式进行一个字符更改。
100101011 $$$\右箭头$$$ 100100011
对于 $$$k = 1$$$,您还可以更改单个字符。
100101011 $$$\右箭头$$$ 100001011
对于 $$$k = 2$$$,无需进行任何更改。