让我们定义压缩字符串 $$$t$$$ 的操作,该字符串由 $$$1$$$ 到 $$$9$$$ 之间至少 $$$2$$$ 数字组成,如下所示:
- 将其拆分为偶数个非空子字符串 - 让这些子字符串为 $$$t_1, t_2, \dots, t_m$$$ (因此,$$$t = t_1 + t_2 + \dots + t_m$$$,其中 $$$+$$$ 是串联操作);
- 写入字符串 $$$t_2$$$ $$$t_1$$$ 次,然后写入字符串 $$$t_4$$$ $$$t_3$$$ 次,依此类推。
例如,对于字符串“12345”,可以执行以下操作:将其拆分为(“1”、“23”、“4”、“5”),并写入“235555”。
让字符串 $$$t$$$ 的函数 $$$f(t)$$$ 返回通过该过程可以获得的字符串的最小长度。
给定一个字符串 $$$s$$$,其中包含从 $$$1$$$ 到 $$$9$$$ 的 $$$n$$$ 数字,以及一个整数 $$$k$$$。计算 $$$f$$$ 中长度恰好为 $$$k$$$ 的 $$$s$$$ 的所有连续子串的函数值。
输入
第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \le k \le n \le 2 \cdot 10^5$$$)。
第二行包含字符串 $$$s$$$ ($$$|s| = n$$$),仅包含从 $$$1$$$ 到 $$$9$$$ 的数字。
输出
输出 $$$n - k + 1$$$ 整数 — $$$f(s_{1,k}), f(s_{2,k+1}), \dots, f(s_{n - k + 1, n})$$$。
示例
输入 #1
4 4 5999
输出 #1
14
输入 #2
10 3 1111111111
输出 #2
2 2 2 2 2 2 2 2
输入 #3
11 4 49998641312
输出 #3
12 18 17 15 12 7 7 2