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 to 'Ninjas (Hard)'


You're not logged in! Click here to login


Submitting .cpp to 'Ninjas (Hard)'


You're not logged in! Click here to login


Compile Errors


							
Time Limit: 2 Seconds
Memory Limit: 1024MB
No. of ACs: 2
Your best score: 0
Source: TROC 24 (oolimry, errorgorn)

Subtask Score
1 100