Преподаватели ЛКШ решили посадить \(n\) деревьев в ряд, причём было решено сажать только дубы и ели. Для этого они составили план, который можно представить в виде двоичной строки \(s\) длины \(n\). Если \(s_i = 0\), то \(i\)-м деревом в ряду должен быть дуб, а если \(s_i = 1\), то \(i\)-м деревом в ряду должна быть ель.
День посадки деревьев уже завтра, а послезавтра в ЛКШ приедет проверяющий. Проверяющий очень любит природу, и он оценит красоту ряда деревьев следующим образом:
- Он вычислит \(l_0\) как максимальное количество подряд идущих дубов в ряду (максимальная подстрока из нулей в плане \(s\)). Если в ряду нет дубов, то \(l_0 = 0\).
- Он вычислит \(l_1\) как максимальное количество подряд идущих елей в ряду (максимальная подстрока из единиц в плане \(s\)). Если в ряду нет елей, то \(l_1 = 0\).
- Красота ряда деревьев будет равна \(a \cdot l_0 + l_1\) для некоторого \(a\) — любимого числа проверяющего.
Преподаватели знают значение параметра \(a\), но не могут сказать его вам из соображений безопасности. Они готовы сказать вам лишь то, что \(a\) является целым числом от \(1\) до \(n\).
Поскольку деревья ещё не посажены, преподаватели решили изменить вид не более чем \(k\) деревьев на противоположный (то есть изменить \(s_i\) с \(0\) на \(1\) или с \(1\) на \(0\) в плане), чтобы максимизировать красоту ряда деревьев по мнению проверяющего.
Для каждого целого \(j\) от \(1\) до \(n\) найдите независимо ответ на следующий вопрос:
- Какой максимальной красоты ряда деревьев могут добиться преподаватели, изменив вид не более чем \(k\) деревьев, если любимое число проверяющего \(a\) равно \(j\)?
Выходные данные
Для каждого набора входных данных выведите \(n\) чисел, \(j\)-е (\(1 \le j \le n\)) из которых — максимальная красота ряда деревьев после не более, чем \(k\) изменений, если для вычисления красоты используется \(a = j\).
Примечание
В первом наборе входных данных не разрешаются изменения, поэтому всегда выполняется \(l_0 = 0\) и \(l_1 = 3\). Таким образом, вне зависимости от значения \(a\), красота ряда деревьев будет равна \(3\).
Во втором наборе входных данных для \(a \in \{1, 2\}\) преподаватели могут, например, изменить план \(s\) на \(0111\) (изменив \(s_4\)), а для \(a \in \{3, 4\}\) — на \(0010\) (изменив \(s_2\)). В таком случае, красота аллеи для каждого \(a\) вычисляется следующим образом:
- Для \(a = 1\): \(l_0 = 1\), \(l_1 = 3\). Красота аллеи равна \(1\cdot 1 + 3 = 4\).
- Для \(a = 2\): \(l_0 = 1\), \(l_1 = 3\). Красота аллеи равна \(2\cdot 1 + 3 = 5\).
- Для \(a = 3\): \(l_0 = 2\), \(l_1 = 1\). Красота аллеи равна \(3\cdot 2 + 1 = 7\).
- Для \(a = 4\): \(l_0 = 2\), \(l_1 = 1\). Красота аллеи равна \(4\cdot 2 + 1 = 9\).
Можно показать, приведённые выше изменения являются оптимальными для всех \(a\) от \(1\) до \(4\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
3 0
111
4 1
0110
5 0
10000
6 2
101101
7 1
0001101
|
3 3 3
4 5 7 9
5 9 13 17 21
6 9 13 17 21 25
7 10 13 17 21 25 29
|