Роботи

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

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

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

Input

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

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

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

Output

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

Examples

Note

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

Scoring

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

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

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