← 返回题目列表

Codeforces · 2004/G

G. 子串压缩

中文机器翻译题面 查看原题

让我们定义压缩字符串 $$$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