codeforces#P1575H. Holiday Wall Ornaments

Holiday Wall Ornaments

Description

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$.

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$.

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$.

Input

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$.

Output

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$.

Samples

9 3
100101011
101
1 1 0 1 6 -1 -1 -1

Note

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.