Let's define the operation of compressing a string $t$, consisting of at least $2$ digits from $1$ to $9$, as follows:

• split it into an even number of non-empty substrings — let these substrings be $t_1, t_2, \dots, t_m$ (so, $t = t_1 + t_2 + \dots + t_m$, where $+$ is the concatenation operation);
• write the string $t_2$ $t_1$ times, then the string $t_4$ $t_3$ times, and so on.

For example, for a string "12345", one could do the following: split it into ("1", "23", "4", "5"), and write "235555".

Let the function $f(t)$ for a string $t$ return the minimum length of the string that can be obtained as a result of that process.

You are given a string $s$, consisting of $n$ digits from $1$ to $9$, and an integer $k$. Calculate the value of the function $f$ for all contiguous substrings of $s$ of length exactly $k$.

Input

The first line contains two integers $n$ and $k$ ($2 \le k \le n \le 2 \cdot 10^5$).

The second line contains the string $s$ ($|s| = n$), consisting only of digits from $1$ to $9$.

Output

Output $n - k + 1$ integers — $f(s_{1,k}), f(s_{2,k+1}), \dots, f(s_{n - k + 1, n})$.

见题面 Input 部分

见题面 Output 部分