В одной стране все населённые пункты являются деревнями и расположены вдоль длинной прямой дороги. Всего вдоль дороги имеется n остановок, расстояние между любыми двумя соседними остановками равно одному километру. Рядом с некоторыми остановками расположены деревни.
Министерство транспорта решило запустить между деревнями рейсовые автобусы, ровно по одному маршруту из каждой деревни. Планируется, что автобус будет выезжать из деревни и двигаться направо вдоль дороги (в сторону увеличения номеров остановок) до тех пор, пока не встретит k деревень, либо не доедет до последней. После этого автобус будет возвращаться в начальную деревню. Так, для самой последней деревни автобус проедет расстояние 0 (направо, ему, конечно, ехать некуда, и, казалось бы, он вообще никому не нужен, но этот вопрос остаётся за рамками данной задачи). Необходимо посчитать длину маршрута каждого автобуса.
В первой строке входных данных находится целое число k (1 ≤ k ≤ 300 000) — количество деревень правее стартовой, которые должен посетить каждый автобус.
Во второй строке следует строка s, состоящая только из символов из '0' и '1', — описание дороги. Если i-й символ строки равен '1', то рядом с i-й остановкой есть деревня, а если '0', то нет. Гарантируется, что всегда есть хотя бы одна деревня, то есть s содержит не менее одного символа '1'. Длина строки s не превосходит 300 000 символов.
Пусть всего во входных данных m деревень, то есть m символов строки s равны '1'. Пронумеруем деревни слева направо вдоль дороги, то есть от начала строки s к концу. Необходимо вывести ровно m целых чисел, i-е из которых должно быть равно длине маршрута автобуса, выезжающего из i-й деревни.
2
101101
6 6 4 0
1
10010001000
6 8 0
10
111
4 2 0
Рассмотрим первый пример.
