数直線上に $n$ 匹の蟻がおり、$i$ 番目の蟻は座標 $i$ に位置しています。各蟻は右（座標が増加する方向）または左（座標が減少する方向）を向いています。蟻は非常に小さいため、点として扱うことができます。

合図とともに、すべての蟻は同じ一定の速度で、向いている方向に歩き始めます。2 匹の蟻が衝突すると（同じ座標に到達すると）、それらは互いに跳ね返ります。つまり、両方の蟻が進行方向を変えて歩き続けます。ある程度の時間が経過すると、それ以降は衝突が起こらなくなることが証明できます。各蟻について、他の蟻と何回衝突するかを計算するプログラムを作成してください。

入力

標準入力の1行目には、蟻の数を表す整数 $n$ ($1 \le n \le 300\,000$) が与えられます。

2行目には、'L' と 'P' のみからなる長さ $n$ の文字列が与えられます。$i$ 番目の文字が 'L' である場合、$i$ 番目の蟻は最初左を向いており、'P' である場合、その蟻は最初右を向いています。

出力

標準出力の1行に、$n$ 個の整数を空白区切りで出力してください。$i$ 番目の数値は、$i$ 番目の蟻が衝突する回数である必要があります。

入出力例

入力 1

6
LPPLPL

出力 1

0 1 3 3 2 1

注記

例の解説：1番目の蟻は最初左を向いており、他のどの蟻とも衝突しません。最後の蟻は座標 5.5 で5番目の蟻と衝突し、その後右へ歩き始め、二度と衝突しません。3番目の蟻は座標 3.5 で4番目の蟻と衝突した後、左へ歩き始めます。2番目の蟻は座標 3 で3番目の蟻と衝突し、その後左へ向きを変えて歩き続けます。