#P1575H. Holiday Wall Ornaments

Holiday Wall Ornaments

No submission language available for this problem.

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.