Козак Вус придбав дуже цікаву гру. Вона складається зі стрічки з $n$ клітинок, пронумерованих зліва направо від $1$ до $n$, у кожній клітинці знаходиться рівно один робот. Також на кожній клітинці написана літера \texttt{`L'} або \texttt{`R'}. За одну секунду усі роботи на клітинках з літерою \texttt{`L'} рухаються на одну клітинку вліво, а роботи на клітинках з літерою \texttt{`R'} --- на одну клітинку вправо. Якщо після кроку робот знаходиться за межами стрічки, він стає неактивним і \textbf{більше не бере участь в грі}. Козак Вус планує грати рівно $t$ секунд. Йому цікаво, скільки роботів буде знаходитися на кожній клітинці через $t$ секунд. \InputFile Перший рядок містить єдине ціле число $n$ ($1 \leq n \leq 10^6$)~--- кількість клітинок у грі, яку придбав Козак Вус. Другий рядок містить $n$ символів, кожен з яких є літерою \texttt{`L'} або літерою \texttt{`R'}, $i$-ий символ задає символ в клітинці номер $i$. Третій рядок містить єдине ціле число $t$ ($1 \leq t \leq 10^{18}$)~--- тривалість гри в секундах. \OutputFile Виведіть $n$ чисел, $i$-е число повинно дорівнювати кількості роботів в клітинці номер $i$ через $t$ секунд. \Note У першому прикладі через одну секунду відповідь буде такою $[1, 2, 0]$: робот першої клітинки перейшов у другу, робот з другої у першу, робот з третьої у другу. Ще через одну секунду відповідь буде такою: $[2, 1, 0]$: робот з першої клітинки перейшов у другу, два роботи з другої клітинки перейшли у першу. \Scoring \begin{enumerate} \item ($17$ балів) $1 \leq n, t \leq 10^3$; \item ($34$ бали) $1 \leq n \leq 10^3$; \item ($49$ балів) Без додаткових обмежень. \end{enumerate}