Sur une droite numérique se trouvent $n$ fourmis, la $i$-ième étant située au point $i$. Chaque fourmi regarde vers la droite (dans le sens des coordonnées croissantes) ou vers la gauche (dans le sens des coordonnées décroissantes). Les fourmis sont si petites que nous pouvons les considérer comme des points.

Au signal, toutes les fourmis commencent à marcher à une vitesse unitaire constante dans la direction vers laquelle elles regardent. Si deux fourmis entrent en collision (se retrouvent au même point), elles rebondissent l'une sur l'autre, c'est-à-dire qu'elles changent toutes deux de direction et continuent leur chemin. On peut démontrer qu'après un certain temps, il n'y aura plus aucune collision. Êtes-vous capable d'écrire un programme qui calcule, pour chaque fourmi, combien de fois elle rebondira sur d'autres fourmis ?

Entrée

La première ligne de l'entrée standard contient un entier $n$ ($1 \le n \le 300\,000$), représentant le nombre de fourmis.

La deuxième ligne de l'entrée standard contient un mot de longueur $n$ composé uniquement des caractères « L » et « P ». Si la $i$-ième lettre de ce mot est « L », alors la $i$-ième fourmi regarde initialement vers la gauche. Sinon, si cette lettre est « P », la fourmi regarde vers la droite.

Sortie

La seule ligne de la sortie standard doit contenir $n$ nombres séparés par des espaces. Le $i$-ième de ces nombres doit être égal au nombre de rebonds de la $i$-ième fourmi.

Exemples

Entrée 1

6
LPPLPL

Sortie 1

0 1 3 3 2 1

Remarque

La première fourmi regarde initialement vers la gauche et ne rebondira jamais sur aucune autre. La dernière fourmi entrera en collision avec la cinquième fourmi au point 5,5, après quoi elle commencera à marcher vers la droite et ne s'arrêtera jamais. La troisième fourmi, après avoir rebondi sur la quatrième au point 3,5, commencera à marcher vers la gauche. La deuxième fourmi rebondira sur elle au point 3, après quoi elle se tournera vers la gauche et ne cessera jamais de marcher.