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\).
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\).
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.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
9 3
100101011
101
|
1 1 0 1 6 -1 -1 -1
|