在数轴上有 $n$ 只蚂蚁，第 $i$ 只蚂蚁位于位置 $i$。每只蚂蚁都面向右方（坐标增加的方向）或左方（坐标减小的方向）。蚂蚁非常小，可以看作是点。

随着信号发出，所有蚂蚁都以相同的单位速度向它们面向的方向行进。如果两只蚂蚁相撞（位于同一位置），它们会互相反弹，即两者都改变行进方向并继续行进。可以证明，经过一段时间后，将不再发生任何碰撞。你能写一个程序，计算每只蚂蚁与其他蚂蚁碰撞的次数吗？

第一行包含一个整数 $n$ ($1 \le n \le 300\,000$)，表示蚂蚁的数量。

第二行包含一个长度为 $n$ 的字符串，仅由字符 ‘L’ 和 ‘P’ 组成。如果第 $i$ 个字符是 ‘L’，则第 $i$ 只蚂蚁初始面向左方。否则，如果字符是 ‘P’，则该蚂蚁面向右方。

在唯一的一行中输出 $n$ 个由空格分隔的整数。其中第 $i$ 个数应等于第 $i$ 只蚂蚁的碰撞次数。

样例

输入格式 1

6
LPPLPL

输出格式 1

0 1 3 3 2 1

说明

第一只蚂蚁初始面向左方，永远不会与其他任何蚂蚁碰撞。最后一只蚂蚁会在位置 $5.5$ 与第五只蚂蚁碰撞，之后它将向右行进，且永远不会再发生碰撞。第三只蚂蚁在位置 $3.5$ 与第四只蚂蚁碰撞后，开始向左行进。第二只蚂蚁会在位置 $3$ 与它碰撞，之后转向左方并一直行进下去。