问题陈述
N 玩家编号 1 通过 N 正在玩多人格斗游戏。 当比赛开始时, N 玩家 输入 立刻响起。 最初,每个玩家的 比赛期间发生 分数 本实验的 is 0.
然后, M 事件。 每个事件都有类型 1 或输入 2 描述如下:
- 类型 1:以以下格式表示。 玩家 x 攻击 玩家 y.
1 x y
- 类型 2:以以下格式表示。 玩家 z 退出 的戒指。
2 z
当玩家退出擂台时,会立即发生以下事件:
- 退出玩家的分数减少 1.
- 如果退出的玩家自上次进入以来至少受到过一次攻击,则最后一次进行此类攻击的玩家的分数增加 1.
- 然后,玩家再次进入擂台。
打印每个玩家的最终得分。
约束
- 所有输入值均为整数。
- 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
输入
输入由标准输入按以下格式给出:
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,打印最终得分 S_i 玩家的 i 采用以下格式,以空格分隔:
S_1 S_2 \ldots S_N
示例输入 1
4 6 1 2 3 1 4 3 2 3 1 2 1 2 2 2 3
示例输出 1
0 -1 -2 1
比赛开始时, 4 选手进入擂台,选手得分为 (S_1, S_2, S_3, S_4) = (0, 0, 0, 0)。 然后,在比赛期间发生以下事件:
- 在 1-st 事件,玩家 2 攻击玩家 3.
- 在 2-nd 事件,玩家 4 攻击玩家 3.
- 在 3-rd 事件,玩家 3 退出,因此他们的分数减少了 1。 由于玩家 3的最后一个入口(即自比赛开始后),他们在 1-st 和 2-nd 事件。其中最后一张是玩家制作的 4,因此他们的分数增加了 1。 随后,玩家 3 再次进入铃声。
- 在 4第一个事件,玩家 2 攻击玩家 1.
- 在 5第一个事件,玩家 2 退出,因此他们的分数减少了 1。 由于玩家 2的最后一个入口(即自比赛开始以来),他们从未受到攻击。随后,玩家 2 再次进入铃声。
- 在 6第一个事件,玩家 3 退出,因此他们的分数减少了 1。 由于玩家 3的最后一个入口(即自 3-rd 事件),他们从未受到攻击。 随后,玩家 3 再次进入铃声。
选手们的最终成绩为 (S_1, S_2, S_3, S_4) = (0, -1, -2, 1).
示例输入 2
5 20 1 2 5 1 4 5 2 2 1 4 1 1 3 1 1 3 2 1 5 4 1 4 5 1 3 1 1 1 2 1 4 5 1 3 2 1 5 2 1 3 2 1 5 4 2 1 1 4 5 1 5 1 2 3 2 3
示例输出 2
-1 -1 -1 0 0