Казак Ус приобрел очень интересную игру. Она состоит из ленты с $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}