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.