/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
問題文
N 人のプレイヤーがカードを使ったゲームをします。
最初、山札に M 枚のカードがあり、場札は 0 枚、各プレイヤーの手札も 0 枚です。
各カードには +, 0, - のいずれかの記号が書かれています。山札の上から i 枚目のカードにかかれている記号は S_i です。
ゲームでは、プレイヤー 1,2,\ldots,N-1,N,1,2,\ldots の順に手番がめぐり、以下を繰り返します。
- 山札が 0 枚ならばゲームを終了する。そうでないとき、手番のプレイヤーは山札の一番上のカードを引き、手札に加える。その後、そのカードにかかれていた記号に応じて以下を行う。
+が書かれていた場合、場札を全て自分の手札に加える0が書かれていた場合、何もしない-が書かれていた場合、自分の手札を全て場札に移す
ゲームが終了したときの、各プレイヤーの手札の枚数を求めてください。
制約
- 2 \leq N \leq 2\times 10^5
- 1 \leq M \leq 2\times 10^5
- S_i は
+,0,-のいずれか
入力
入力は以下の形式で標準入力から与えられる。
N M S_1 S_2 \ldots S_M
出力
N 行出力せよ。
i 行目には、ゲームが終了したときのプレイヤー i の手札の枚数を出力せよ。
入力例 1
3 6 000--+
出力例 1
0 0 6
ゲームは次のように進行します。
- プレイヤー 1 が
0の書かれたカードを引き、手札に加える。プレイヤー 1 の手札は 1 枚となる。 - プレイヤー 2 が
0の書かれたカードを引き、手札に加える。プレイヤー 2 の手札は 1 枚となる。 - プレイヤー 3 が
0の書かれたカードを引き、手札に加える。プレイヤー 3 の手札は 1 枚となる。 - プレイヤー 1 が
-の書かれたカードを引き、手札に加える。その後、手札を全て場札に移す。プレイヤー 1 の手札は 0 枚となり、場札は 2 枚となる。 - プレイヤー 2 が
-の書かれたカードを引き、手札に加える。その後、手札を全て場札に移す。プレイヤー 2 の手札は 0 枚となり、場札は 4 枚となる。 - プレイヤー 3 が
+の書かれたカードを引き、手札に加える。その後、場札を全て手札に加える。プレイヤー 3 の手札は 6 枚となり、場札は 0 枚となる。 - 山札がなくなったのでゲームを終了する。
入力例 2
2 6 ++++++
出力例 2
3 3
入力例 3
7 20 ++-0+-0++-++0-+0-0-0
出力例 3
6 3 0 4 0 2 0
Problem Statement
N players will play a game using cards.
Initially, the first pile contains M cards, the second pile contains 0 cards, and each player has 0 cards.
Each card has one of the symbols +, 0, and - written on it. The symbol on the i-th card from the top of the initial first pile is S_i.
In the game, the players take turns doing the following, in this order: player 1, player 2, \ldots, player N-1, player N, player 1, player 2, \dots
- If the first pile contains 0 cards, end the game. Otherwise, the current player draws the top card from the first pile, and adds it to the player's hand. Then, according to the symbol written on that card, the player does the following.
- If
+is written, add all cards in the second pile to the player's hand. - If
0is written, do nohing. - If
-is written, move all cards in the player's hand to the second pile.
- If
Find the number of cards in each player's hand at the end of the game.
Constraints
- 2 \leq N \leq 2\times 10^5
- 1 \leq M \leq 2\times 10^5
- S_i is
+,0, or-.
Input
Input is given from Standard Input in the following format:
N M S_1 S_2 \ldots S_M
Output
Print N lines.
The i-th line should contain the number of cards in player i's hand.
Sample Input 1
3 6 000--+
Sample Output 1
0 0 6
The game proceeds as follows.
- Player 1 draws a
0card and adds it to the hand. Now, player 1 has 1 card. - Player 2 draws a
0card and adds it to the hand. Now, player 2 has 1 card. - Player 3 draws a
0card and adds it to the hand. Now, player 3 has 1 card. - Player 1 draws a
-card, adds it to the hand, and then moves all cards in the hand to the second pile. Now, player 1 has 0 cards, and the second pile has 2 cards. - Player 2 draws a
-card, adds it to the hand, and then moves all cards in the hand to the second pile. Now, player 2 has 0 cards, and the second pile has 4 cards. - Player 3 draws a
+card, adds it to the hand, and then adds all cards in the second pile to the hand. Now, player 3 has 6 cards, and the second pile has 0 cards. - The first pile has no cards, so the game ends.
Sample Input 2
2 6 ++++++
Sample Output 2
3 3
Sample Input 3
7 20 ++-0+-0++-++0-+0-0-0
Sample Output 3
6 3 0 4 0 2 0