CF1575H.Holiday Wall Ornaments

The Winter holiday will be here soon. Mr. Chanek wants to decorate his house's wall with ornaments. The wall can be represented as a binary string $a$ of length $n$. His favorite nephew has another binary string $b$ of length $m$ ($m \leq n$).

Mr. Chanek's nephew loves the non-negative integer $k$. His nephew wants exactly $k$ occurrences of $b$ as substrings in $a$.

However, Mr. Chanek does not know the value of $k$. So, for each $k$ ($0 \leq k \leq n - m + 1$), find the minimum number of elements in $a$ that have to be changed such that there are exactly $k$ occurrences of $b$ in $a$.

A string $s$ occurs exactly $k$ times in $t$ if there are exactly $k$ different pairs $(p,q)$ such that we can obtain $s$ by deleting $p$ characters from the beginning and $q$ characters from the end of $t$.

寒假即将到来。Chanek 先生想用装饰品来装点自家墙壁。墙壁可表示为一个长度为 $n$ 的 01 字符串 $a$。他最喜爱的侄子拥有另一个长度为 $m$（$m \leq n$）的 01 字符串 $b$。

Chanek 先生的侄子钟爱某个非负整数 $k$，他希望字符串 $b$ 在 $a$ 中恰好作为子串出现 $k$ 次。

然而，Chanek 先生并不知道 $k$ 的具体取值。因此，请对每个 $k$（$0 \leq k \leq n - m + 1$），求出：为使 $b$ 在 $a$ 中恰好出现 $k$ 次，所需修改 $a$ 中元素的最小次数。

字符串 $s$ 在字符串 $t$ 中恰好出现 $k$ 次，是指：恰好存在 $k$ 个不同的数对 $(p,q)$，使得从 $t$ 的开头删去 $p$ 个字符、结尾删去 $q$ 个字符后，所得字符串恰好为 $s$。

The first line contains two integers $n$ and $m$ ($1 \leq m \leq n \leq 500$) — size of the binary string $a$ and $b$ respectively.

The second line contains a binary string $a$ of length $n$.

The third line contains a binary string $b$ of length $m$.

第一行包含两个整数 $n$ 和 $m$（$1 \leq m \leq n \leq 500$），分别表示二进制字符串 $a$ 和 $b$ 的长度。

第二行包含一个长度为 $n$ 的二进制字符串 $a$。

第三行包含一个长度为 $m$ 的二进制字符串 $b$。

Output $n - m + 2$ integers — the $(k+1)$-th integer denotes the minimal number of elements in $a$ that have to be changed so there are exactly $k$ occurrences of $b$ as a substring in $a$.

输出 $n - m + 2$ 个整数——其中第 $(k+1)$ 个整数表示：为使字符串 $a$ 中恰好出现 $k$ 次子串 $b$，所需修改的 $a$ 中元素的最少个数。

For $k = 0$, to make the string $a$ have no occurrence of 101, you can do one character change as follows.

100101011 $\rightarrow$ 100100011

For $k = 1$, you can also change a single character.

100101011 $\rightarrow$ 100001011

For $k = 2$, no changes are needed.

当 $k = 0$ 时，为使字符串 $a$ 不包含子串 101，可进行如下单字符修改：

100101011 $\rightarrow$ 100100011

当 $k = 1$ 时，同样只需修改一个字符：

100101011 $\rightarrow$ 100001011

当 $k = 2$ 时，无需任何修改。