Роботи#10445

Роботи

1 секунда

256 мегабайтів

Середня

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

За одну секунду усі роботи на клітинках з літерою 'L' рухаються на одну клітинку вліво, а роботи на клітинках з літерою 'R' — на одну клітинку вправо. Якщо після кроку робот знаходиться за межами стрічки, він стає неактивним і більше не бере участі у грі.

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

Вхідні дані

Перший рядок містить єдине ціле число $n$ ( $1 \leq n \leq 1 0^{6}$ 1 \leq n \leq 10^6) — кількість клітинок у грі, яку придбав Козак Вус.

Другий рядок містить $n$ символів, кожен з яких є літерою 'L' або літерою 'R', $i$ -й символ задає символ в клітинці номер $i$ .

Третій рядок містить єдине ціле число $t$ ( $1 \leq t \leq 1 0^{18}$ 1 \leq t \leq 10^{18}) — тривалість гри в секундах.

Вихідні дані

Виведіть $n$ чисел, $i$ -те число повинно дорівнювати кількості роботів в клітинці номер $i$ через $t$ секунд.

Приклади

Приклад 1

Приклад 2

Примітка

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

Оцінювання

( $17$ балів) $1 \leq n, t \leq 1 0^{3}$ 1 \leq n, t \leq 10^3;
( $34$ балів) $1 \leq n \leq 1 0^{3}$ 1 \leq n \leq 10^3;
( $49$ балів) Без додаткових обмежень.