I. Swap(Mohamed, !Mohamed)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You have $$$n$$$ boxes. You are given a binary string $$$boxes$$$ of length $$$n$$$, where $$$boxes_i$$$ is '$$$0$$$' if the $$$i_{th}$$$ box is empty, and '$$$1$$$' if it contains one ball.

In one operation, you can move one ball from a box to an adjacent box. $$$Box_i$$$ is adjacent to $$$box_j$$$ if $$$abs(i - j) = 1$$$.

Note that after doing so, there may be more than one ball in some boxes.

Print an array $$$answer$$$ of size $$$n$$$, where $$$answer_i$$$ is the minimum number of operations needed to move all the balls to the $$$i_{th}$$$ box.

Each $$$answer_i$$$ is calculated considering the initial state of the boxes.

Input

The first line contains a single integer $$$n$$$ $$$(1 \leq n \leq 2×10^5)$$$ — the number of boxes.

The second line contains a single string $$$boxes$$$.

Output

Print an array $$$answer$$$ of size $$$n$$$, where $$$answer_i$$$ is the minimum number of operations needed to move all the balls to the $$$i_{th}$$$ box.

Examples
Input
3
110
Output
1 1 3
Input
6
001011
Output
11 8 5 4 3 4