30748번 - стандартный ввод 다국어

В одной стране все населённые пункты являются деревнями и расположены вдоль длинной прямой дороги. Всего вдоль дороги имеется $n$ остановок, расстояние между любыми двумя соседними остановками равно одному километру. Рядом с некоторыми остановками расположены деревни.

Министерство транспорта решило запустить между деревнями рейсовые автобусы, ровно по одному маршруту из каждой деревни. Планируется, что автобус будет выезжать из деревни и двигаться направо вдоль дороги (в сторону увеличения номеров остановок) до тех пор, пока не встретит $k$ деревень, либо не доедет до последней. После этого автобус будет возвращаться в начальную деревню. Так, для самой последней деревни автобус проедет расстояние $0$ (направо, ему, конечно, ехать некуда, и, казалось бы, он вообще никому не нужен, но этот вопрос остаётся за рамками данной задачи). Необходимо посчитать длину маршрута каждого автобуса.

В первой строке входных данных находится целое число $k$ ($1 \leq k \leq 300\,000$) --- количество деревень правее стартовой, которые должен посетить каждый автобус.

Во второй строке следует строка $s$, состоящая только из символов из '0' и '1', --- описание дороги. Если $i$-й символ строки равен '1', то рядом с $i$-й остановкой есть деревня, а если '0', то нет. Гарантируется, что всегда есть хотя бы одна деревня, то есть $s$ содержит не менее одного символа '1'. Длина строки $s$ не превосходит $300\,000$ символов.

Пусть всего во входных данных $m$ деревень, то есть $m$ символов строки $s$ равны '1'. Пронумеруем деревни слева направо вдоль дороги, то есть от начала строки $s$ к концу. Необходимо вывести ровно $m$ целых чисел, $i$-е из которых должно быть равно длине маршрута автобуса, выезжающего из $i$-й деревни.

Рассмотрим первый пример.

1. Автобус из деревни, расположенной у остановки $1$, будет ездить до деревни, расположенной у остановки $4$, потому что это вторая деревня на его пути.
2. Автобус из деревни, расположенной у остановки $3$, будет ездить до деревни, расположенной у остановки $6$, потому что это вторая деревня на его пути.
3. Автобус из деревни, расположенной у остановки $4$, будет ездить до деревни, расположенной у остановки $6$, потому что это последняя деревня вдоль дороги.
4. Автобус из деревни, расположенной у остановки $6$, будет ездить до деревни, расположенной у остановки $6$, потому что это последняя деревня вдоль дороги.