在數線上站著 $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

說明 1

第一隻螞蟻初始面向左方，永遠不會與任何其他螞蟻碰撞。最後一隻螞蟻會在點 $5.5$ 與第五隻螞蟻碰撞，隨後向右移動並永遠不會再碰撞。第三隻螞蟻在點 $3.5$ 與第四隻螞蟻碰撞後，開始向左移動。第二隻螞蟻會在點 $3$ 與其碰撞，隨後轉向左方並永遠持續移動。