C. Cryptographic Trace
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

In the distant future, information is the most valuable resource. You are an elite cryptographer in the Intergalactic Intelligence Agency. Recently, a binary signal $$$s$$$ of length $$$n$$$ was intercepted—presumably a message from an enemy organization. According to intelligence, they use a special code $$$t$$$ of length $$$m$$$, which is inserted into transmitted signals to convey secret commands.

But there is a problem: due to cosmic interference, some bits may have been randomly corrupted. Now you face an important task: change the minimum number of bits in the signal $$$s$$$ so that the substring $$$t$$$ appears exactly $$$k$$$ times in it, for every possible $$$k$$$ from $$$0$$$ to $$$n - m + 1$$$.

The minimum number of changes is the number of 0 → 1 or 1 → 0 replacements you need to make in $$$s$$$ so that exactly $$$k$$$ occurrences of the substring $$$t$$$ appear in the modified version of $$$s$$$.

Headquarters is waiting for your report: for each $$$k$$$, what is the minimum cost (in changes) to obtain $$$k$$$ occurrences of $$$t$$$?

Input

The first line contains two integers $$$n$$$ and $$$m$$$—the lengths of the binary strings $$$a$$$ and $$$b$$$, respectively $$$(1 \le m \le n \le 500)$$$. The second line contains the binary string $$$s$$$ of length $$$n$$$. The third line contains the binary string $$$t$$$ of length $$$m$$$.

Output

Print $$$n - m + 2$$$ integers: Let $$$k$$$ be the number of occurrences of string $$$b$$$ in string $$$a$$$. Then the $$$(k+1)$$$-th printed number should be the minimum number of changes (replacements of 0 with 1 or 1 with 0) in string $$$s$$$ that are necessary so that string $$$t$$$ appears exactly $$$k$$$ times as a substring in $$$s$$$.

Example
Input
5 2
01010
10
Output
2 1 0 -1 -1
Note

k = 0 (to remove all occurrences of 10): You can change 1 symbol, for example, 01010 → 00000, then 10 will not occur at all. Answer: 2.

k = 1 (to leave one substring 10): The string 01010 can be left as is and one of the two occurrences can be changed. For example: 01010 → 01110. Answer: 1.

k = 2 (leave both occurrences): The original string already fits. No changes are needed. Answer: 0.