Circle Handshakes - KhIMIO

At the start, every person has made $0$ handshakes. Let $H_j$ denote the current total number of handshakes of person $j$ at any moment. On the $i$-th turn:

• If $H_i \ge A_i$, the $i$-th person does nothing on this turn.

• Otherwise, the $i$-th person leaves their position and starts moving around the circle in the direction given by $S_i$:

  • If $S_i = L$, they move anticlockwise: first to person $i-1$, then $i-2$, and so on. When they reach person $1$, they continue from person then and so on.

Visiting people one by one in that order, each time they meet a person $x \ne i$ and still have $H_i < A_i$, they perform a handshake with $x$ (this increases both $H_i$ and $H_x$ by $1$). They continue until $H_i = A_i$, then return to their original position.

Note. The target $A_i$ refers to the overall number of handshakes for person $i$. Handshakes received during other people's turns count toward $H_i$. If, by the start of turn $i$, $H_i \ge A_i$, person $i$ skips their turn entirely.

Determine the final number of handshakes $H_1, H_2, \ldots, H_N$ after all $N$ turns are completed.

Input Format

First line contains one integer $N \ (2 \leq N \leq 5 \cdot 10^5)$⁠.

Second line contains one string consisting of $N$ characters, $S \ (S_i \in \{L, R\})$.

Third line contains $N$ space-separated integers $A_1, A_2, \ldots, A_N \ (0 \leq A_i \leq 10^9)$⁠.

Output Format

Print one line containing $N$ space-separated integers, the answer.

Scoring