On the number line, there are $n$ ants, with the $i$-th ant located at point $i$. Each ant is facing either to the right (in the direction of increasing coordinates) or to the left (in the direction of decreasing coordinates). The ants are small enough that we can treat them as single points.

Upon a signal, all ants start marching at the same unit speed in the directions they are facing. If two ants collide (reach the same point), they bounce off each other, meaning both change their direction of movement and continue marching. It can be proven that after some time, no more collisions will occur. Can you write a program that calculates how many times each ant will bounce off other ants?

Input

The first line of standard input contains a single integer $n$ ($1 \le n \le 300\,000$), representing the number of ants.

The second line of standard input contains a string of length $n$ consisting only of the characters 'L' and 'P'. If the $i$-th letter of this string is 'L', the $i$-th ant is initially facing left. Otherwise, if the letter is 'P', the ant is facing right.

Output

The only line of standard output should contain $n$ space-separated integers. The $i$-th of these numbers should be equal to the number of bounces of the $i$-th ant.

Examples

Input 1

6
LPPLPL

Output 1

0 1 3 3 2 1

Note

The first ant is initially facing left and will never bounce off any other ant. The last ant will collide with the fifth ant at point $5.5$, after which it will start marching to the right and will never stop. The third ant, after bouncing off the fourth at point $3.5$, will start moving to the left. The second ant will bounce off it at point $3$, after which it will turn left and never stop marching.