Определим операцию сжатия строки \(t\), состоящей из хотя бы \(2\) цифр от \(1\) до \(9\), следующим образом:
- разобьем ее на четное количество непустых подстрок — пусть эти подстроки будут \(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».
Пусть функция \(f(t)\) для строки \(t\) возвращает минимальную длину строки, которую можно будет получить в результате такого процесса.
Дана строка \(s\), состоящая из \(n\) цифр от \(1\) до \(9\), и целое число \(k\). Посчитайте значение функции \(f\) для всех последовательных подстрок \(s\) длины ровно \(k\).
Выходные данные
Выведите \(n - k + 1\) целое число — \(f(s_{1,k}), f(s_{2,k+1}), \dots, f(s_{n - k + 1, n})\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 4
5999
|
14
|
|
2
|
10 3
1111111111
|
2 2 2 2 2 2 2 2
|
|
3
|
11 4
49998641312
|
12 18 17 15 12 7 7 2
|