题目描述

有 $N$ 张卡片和 $N$ 个牌堆。卡片和牌堆分别编号为 $1, 2, \ldots, N$。初始时，第 $i$ 个牌堆中只包含第 $i$ 张卡片。

按顺序对每个 $i = 1, 2, \ldots, Q$ 执行以下操作：

• 将第 $C_i$ 张卡片以及叠在它上面的所有卡片（保持原有顺序）移动到第 $P_i$ 张卡片的上面。保证在操作执行前，第 $C_i$ 张卡片和第 $P_i$ 张卡片位于不同的牌堆中，且第 $P_i$ 张卡片位于某个牌堆的顶部。

求所有操作完成后，每个牌堆中的卡片数量。

输入格式

第一行输入两个整数 $N$、$Q$。

接下来 $Q$ 行，每行输入两个整数 $C_i$、$P_i$。

输出格式

设第 $i$ 个牌堆最终有 $A_i$ 张卡片，依次输出 $A_1, A_2, \ldots, A_N$，以空格分隔。

5 4
1 3
4 5
1 4
4 2

0 3 1 0 1

7 8
3 1
5 4
2 5
5 7
2 3
6 2
3 4
5 1

2 0 0 4 0 0 1

数据范围与提示

对于 $100\%$ 的数据，$1 \leq N, Q \leq 3 \times 10^5$。