En la recta numérica hay $n$ hormigas; la $i$-ésima de ellas se encuentra en el punto $i$. Cada una de las hormigas mira hacia la derecha (en dirección a las coordenadas crecientes) o hacia la izquierda (en dirección a las coordenadas decrecientes). Las hormigas son tan pequeñas que podemos tratarlas como puntos individuales.

A la señal, todas las hormigas comienzan a marchar con una velocidad unitaria constante en la dirección hacia la que miran. Si dos hormigas chocan (se encuentran en el mismo punto), rebotan entre sí, es decir, ambas cambian su dirección de marcha y continúan caminando. Se puede demostrar que, después de cierto tiempo, no ocurrirán más colisiones. ¿Eres capaz de escribir un programa que calcule, para cada hormiga, cuántas veces rebotará contra otras hormigas?

Entrada

En la primera línea de la entrada estándar hay un número entero $n$ ($1 \le n \le 300\,000$), que representa el número de hormigas.

En la segunda línea de la entrada estándar hay una palabra de longitud $n$ que consiste únicamente en los caracteres 'L' y 'P'. Si la $i$-ésima letra de esta palabra es 'L', la $i$-ésima hormiga mira inicialmente hacia la izquierda. De lo contrario, si la letra es 'P', la hormiga mira hacia la derecha.

Salida

En la única línea de la salida estándar debe haber $n$ números separados por espacios individuales. El $i$-ésimo de estos números debe ser igual al número de rebotes de la $i$-ésima hormiga.

Ejemplos

Entrada 1

6
LPPLPL

Salida 1

0 1 3 3 2 1

Nota

La primera hormiga mira inicialmente hacia la izquierda y nunca rebotará contra ninguna otra. La última hormiga chocará con la quinta hormiga en el punto 5.5, tras lo cual comenzará a marchar hacia la derecha y nunca terminará. La tercera hormiga, tras rebotar contra la cuarta en el punto 3.5, comenzará a caminar hacia la izquierda. La segunda hormiga rebotará contra ella en el punto 3, tras lo cual girará hacia la izquierda y nunca dejará de marchar.