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 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