Казак Ус приобрел очень интересную игру. Она состоит из ленты с n клетками, пронумерованных слева направо от 1 до n, в каждой ячейке находится ровно один робот. Также на каждой клеточке написана буква 'L'
или 'R'
.
За одну секунду все работы в ячейках с буквой 'L'
двигаются на одну ячейку влево, а работы в ячейках с буквой 'R'
— на одну ячейку вправо. Если после шага робот находится за пределами ленты, он становится неактивным и больше не участвует в игре.
Казак Ус планирует играть ровно t секунд. Ему интересно, сколько роботов будет находиться на каждой клетке через t секунд.
Первая строка содержит целое число n (1≤n≤106) — количество ячеек в игре, которую приобрел Козак Ус.
Вторая строка содержит n символов, каждый из которых является буквой 'L'
или буквой 'R'
, i-ый символ задает символ в ячейке номер i.
Третья строка содержит целое число t (1≤t≤1018) — продолжительность игры в секундах.
Выведите n чисел, i -ое число должно равняться количеству роботов в ячейке номер i через t секунд.
В первом примере через одну секунду ответ будет такой [1,2,0]: робот из первой клетки перешел во вторую, робот со второй клетки перешел в первую, робот с третьей клетки перешел во вторую. Через одну секунду ответ будет такой: [2,1,0]: робот с первой клетки перешел во вторую, два робота со второй клетки перешли в первую.
(17 баллов) 1≤n,t≤103;
(34 балла) 1≤n≤103;
(49 баллов) Без дополнительных ограничений.