На числовой прямой стоят $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$, после чего повернет влево и больше никогда не столкнется.