The difference between Ninjas (easy) and Ninjas (hard) are the constraints of \(P\).
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:
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?
N Q M_{1}M_{2}…M_{Q} P_{1}P_{2}…P_{Q}
Output \(N\) lines, where the \(i\)-th line is the number of high-fives by the \(i\)-th ninja.
4 4
LURD
0101
3
4
4
3
3 1
U
1
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 |