### Ninjas (Hard)

The difference between Ninjas (easy) and Ninjas (hard) are the constraints of $$P$$.

### 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 \in \{\texttt{0}, \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
0101

### Sample Output 1

3
4
4
3

### Sample Input 2

3 1
U
1

### Sample Output 2

1
2
1

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

 Move 2 Move 4 Ninja 0 1 2 Ninja 1 2 2 Ninja 2 2 2 Ninja 3 1 2

### Submitting .cpp to 'Ninjas (Hard)'

Time Limit: 2 Seconds
Memory Limit: 1024MB
No. of ACs: 2