To make this popular card game more interesting, Cai-Cai has defined a series of rules:

1. Each game starts with player 1, and there are $n$ players who take turns playing in a clockwise direction around a circular table. Initially, they take turns in order. Player $i$ starts with $a_i$ cards in their hand.
2. There are 4 types of cards: Normal (C), Skip (S), Reverse (R), and Draw Two (D). Normal cards have no effect; Skip cards cause the next player to skip their turn; Reverse cards reverse the current order of play, meaning the turn passes to the player who previously played; Draw Two cards force the next player to draw 2 cards and skip their turn. All cards have no restrictions on when they can be played; a player can play any card at any time.
3. If a player runs out of cards, that player immediately exits the game.

Cai-Cai knows the results of the plays in this game, and asks you to tell him how many cards each player has left.

Input

The first line contains two integers $n, m$ ($2 \le n, m \le 2 \times 10^5$), as described. The second line contains $n$ integers $a_i$ ($1 \le a_i \le 2 \times 10^5$). The third line contains a string of length $m$, representing the play results of all players in this game. Among them, C is a Normal card, S is a Skip card, R is a Reverse card, and D is a Draw Two card. It is guaranteed that the order of play is valid and that there are at least two players remaining until the end.

Output

Output $n$ lines, where the $i$-th line contains the final number of cards held by player $i$.

Examples

Input 1

3 6
3 2 3
SRDCCD

Output 1

3
0
3

Note

First, player 1 plays a Skip card, player 2 is skipped, player 3 plays a Reverse card, causing the order of play to reverse. Next, it is player 2's turn, who plays a Draw Two card, causing player 1's card count to increase by 2 and skipping player 1's turn. Next, player 3 and player 2 each play a Normal card. At this point, player 2 runs out of cards, and player 1 plays a Draw Two card, causing player 3's card count to increase by 2. The final card counts are 3, 0, 3.