Роботы

Казак Ус приобрел очень интересную игру. Она состоит из ленты с $n$ клетками, пронумерованных слева направо от $1$ до $n$, в каждой ячейке находится ровно один робот. Также на каждой клеточке написана буква 'L' или 'R'.

За одну секунду все работы в ячейках с буквой 'L' двигаются на одну ячейку влево, а работы в ячейках с буквой 'R' — на одну ячейку вправо. Если после шага робот находится за пределами ленты, он становится неактивным и больше не участвует в игре.

Казак Ус планирует играть ровно $t$ секунд. Ему интересно, сколько роботов будет находиться на каждой клетке через $t$ секунд.

Входные данные

Первая строка содержит целое число $n$ ($1\le n\le 10^6$) — количество ячеек в игре, которую приобрел Козак Ус.

Вторая строка содержит $n$ символов, каждый из которых является буквой 'L' или буквой 'R', $i$-ый символ задает символ в ячейке номер $i$.

Третья строка содержит целое число $t$ ($1\le t\le 10^{18}$) — продолжительность игры в секундах.

Выходные данные

Выведите $n$ чисел, $i$ -ое число должно равняться количеству роботов в ячейке номер $i$ через $t$ секунд.

Примеры

Примечание

В первом примере через одну секунду ответ будет такой $[1,2,0]$: робот из первой клетки перешел во вторую, робот со второй клетки перешел в первую, робот с третьей клетки перешел во вторую. Через одну секунду ответ будет такой: $[2,1,0]$: робот с первой клетки перешел во вторую, два робота со второй клетки перешли в первую.

Оценивание

1. ($17$ баллов) $1\le n,t\le 10^3$;

2. ($34$ балла) $1\le n\le 10^3$;

3. ($49$ баллов) Без дополнительных ограничений.