Роботи#197

Роботи

1 second
256 megabytes
Hard

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

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

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

Input

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

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

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

Output

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

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

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

Scoring

  1. ( балів) 1 \leq n, t \leq 10^3;

  2. ( бали) 1 \leq n \leq 10^3;

  3. ( балів) Без додаткових обмежень.