AT_past18_d 大乱闘

$ 1 $ から $ N $ の番号がついた $ N $ 人のプレイヤーがとある対戦型格闘ゲームで遊びます。 対戦開始時と同時に、 $ N $ 人のプレイヤーはゲーム上でリングに**登場**します。対戦開始時の全プレイヤーの**スコア**は $ 0 $ です。 その後、対戦中に $ M $ 個のイベントが起きます。各イベントは下記のタイプ $ 1 $ またはタイプ $ 2 $ のどちらかです。 - タイプ $ 1 $ : 下記の形式で示される。プレイヤー $ x $ が、プレイヤー $ y $ に**攻撃**する。 > 1 $ x $ $ y $ - タイプ $ 2 $ : 下記の形式で示される。プレイヤー $ z $ がリングから**脱落**する。 > 2 $ z $ プレイヤーがリングから脱落すると、直ちに下記の出来事が起きます。 - 脱落したプレイヤーのスコアが $ 1 $ だけ減少する。 - 脱落したプレイヤーが直前にリングに登場した後に $ 1 $ 回以上攻撃されていた場合、そのうち最後の攻撃を行ったプレイヤーのスコアが $ 1 $ だけ増加する。 - その後、脱落したプレイヤーはリングに再び登場する。 各プレイヤーの最終的なスコアを出力してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ \mathrm{event}_1 $ $ \mathrm{event}_2 $ $ \vdots $ $ \mathrm{event}_M $ $ i = 1, 2, \ldots, M $ について、 $ \mathrm{event}_i $ は $ i $ 番目に起きたイベントを表し、 問題文中に示されたタイプ $ 1 $ とタイプ $ 2 $ のどちらかの形式である。

$ i = 1, 2, \ldots, N $ について、プレイヤー $ i $ の最終的なスコア $ S_i $ を下記の形式で空白区切りで出力せよ。 > $ S_1 $ $ S_2 $ $ \ldots $ $ S_N $

### Sample Explanation 1 対戦開始時、 $ 4 $ 人のプレイヤーがリングに登場し、各プレイヤーのスコアは $ (S_1, S_2, S_3, S_4) = (0, 0, 0, 0) $ です。 その後、対戦中に下記の通りにイベントが起きます。 - $ 1 $ 番目のイベントでは、プレイヤー $ 2 $ がプレイヤー $ 3 $ に攻撃します。 - $ 2 $ 番目のイベントでは、プレイヤー $ 4 $ がプレイヤー $ 3 $ に攻撃します。 - $ 3 $ 番目のイベントでは、プレイヤー $ 3 $ が脱落します。その結果、プレイヤー $ 3 $ のスコアが $ 1 $ だけ減少します。また、プレイヤー $ 3 $ が直前にリングに登場したとき（すなわち、対戦開始時）より後に、プレイヤー $ 3 $ は $ 1 $ 番目と $ 2 $ 番目のイベントで攻撃されているため、そのうち最後の攻撃を行ったプレイヤー $ 4 $ のスコアが $ 1 $ だけ増加します。その後、プレイヤー $ 3 $ は再びリングに登場します。 - $ 4 $ 番目のイベントでは、プレイヤー $ 2 $ がプレイヤー $ 1 $ に攻撃します。 - $ 5 $ 番目のイベントでは、プレイヤー $ 2 $ が脱落します。その結果、プレイヤー $ 2 $ のスコアが $ 1 $ だけ減少します。プレイヤー $ 2 $ が直前にリングに登場したとき（すなわち、対戦開始時）より後に、プレイヤー $ 2 $ は $ 1 $ 回も攻撃されていません。その後、プレイヤー $ 2 $ は再びリングに登場します。 - $ 6 $ 番目のイベントでは、プレイヤー $ 3 $ が脱落します。その結果、プレイヤー $ 3 $ のスコアが $ 1 $ だけ減少します。プレイヤー $ 3 $ が直前にリングに登場したとき（すなわち、 $ 3 $ 番目のイベントの最後）より後に、プレイヤー $ 3 $ は $ 1 $ 回も攻撃されていません。その後、プレイヤー $ 3 $ は再びリングに登場します。 各プレイヤーの最終的なスコアは $ (S_1, S_2, S_3, S_4) = (0, -1, -2, 1) $ となります。 ### Constraints - 入力はすべて整数 - $ 2 \leq N \leq 2 \times 10^5 $ - $ 1 \leq M \leq 2 \times 10^5 $ - $ 1 \leq x, y, z \leq N $ - $ x \neq y $