Ninjas (Easy)

The difference between Ninjas (easy) and Ninjas (hard) are the constraints of $P$. In this version, all $P_j = 1$

Description

As we all know, Mr. Lim is a ninja. Due to the powers of shadow clone jutsu, he also happens to have $N-1$ shadow ninjas that follow him around and mimic his actions. Mr. Lim is the ninja $0$ and the other ninjas are numbered from $1$ to $N-1$. All the ninjas are on an infinitely sized grid, where ninja $i$ initially stands at coordinates $(i,0)$.

Mr. Lim will move a total of $Q$ times. His moves are described by the string $M$.

Suppose that before the $j$-th move, Mr. Lim is currently at cell $(x,y)$. If $M_j$ is equal to:

• $\texttt{L}$: he will move to cell $(x-1,y)$;
• $\texttt{R}$: he will move to cell $(x+1,y)$;
• $\texttt{D}$: he will move to cell $(x,y-1)$;
• $\texttt{U}$: he will move to cell $(x,y+1)$.

After Mr. Lim has moved, ninja $i$ ($1 \le i \le N-1$) will move to occupy the space originally occupied by ninja $(i-1)$. It is guaranteed that no two ninjas will be in the same position after everyone has moved.

The ninjas will perform high-fives based on a binary string $P$ of length $Q$. If $P_j=\texttt{1}$, all ninjas (including Mr. Lim) will perform a high-five after the $j$-th move. All ninjas will high-five every ninja who is close to him. Two ninjas on $(x_a,y_a)$ and position $(x_b,y_b)$ respectively are close if $|x_a-x_b|+|y_a-y_b|=1$.

After all $Q$ moves, you want to know for each ninja, how many times has he high-fived in total?

Constraints

• $1 \le N,Q \le 50\;000$
• $|M|=|P|=Q$
• $M_j \in \{\texttt{L},\texttt{R},\texttt{D},\texttt{U} \}$
• $P_j = \texttt{1}$

Input

N Q
M1M2…MQ
P1P2…PQ

Output

Output $N$ lines, where the $i$-th line is the number of high-fives by the $i$-th ninja.

Sample Input 1

4 4
LURD
1111

Sample Output 1

6
8
8
6

Sample Input 2

3 1
U
1

Sample Output 2

1
2
1

Explanation

In the first sample, the number of high-fives by each ninja after each move is given by the following table.