在这个不稳定的世界里，不畏惧不稳定的人终将获胜。因此，举办一场重视“波动最大选手”（Most Fluctuated Player, MFP）的比赛是很自然的，MFP 指的是在比赛期间排名波动最大的选手。

国际变更促进竞赛（International Change Promotion Contest, ICPC）就是这样一场比赛。在这场比赛中，有 $N$ 名参赛者挑战 $Q$ 道测验题。比赛使用两种代币：积分和硬币。积分用于评估测验能力本身，而硬币用于评估波动情况。因此，硬币更为重要，因为它直接影响最终结果。

每位参赛者初始时拥有 0 积分和 0 硬币。回答第 $i$ 道测验题的参赛者将获得 $p_i$ 积分。注意 $p_i$ 可以为负数；这没关系，因为比赛的重点是不稳定性（硬币），而不是积分。每次测验结束后都会计算积分排名，每位参赛者根据其积分排名的波动获得硬币：如果一名参赛者的积分排名从 $a$ 变为 $b$，该参赛者将获得 $|a - b|$ 枚硬币，其中 $|x|$ 表示 $x$ 的绝对值。参赛者的积分排名定义为 1 加上积分（严格）大于该参赛者积分的参赛者人数。例如，初始时，所有参赛者的排名均为 1，因为所有参赛者都有 0 积分，因此没有人比其他人拥有更多的积分。

作为 ICPC 的组织者，你有一份过去比赛的记录。该记录包含关于 $Q$ 道测验的信息：第 $i$ 道测验由参赛者 $a_i$ 回答，得分为 $p_i$。但记录中不包含最终结果：即每位参赛者最终获得的硬币数量。你的任务是编写一个程序，根据记录计算出 $Q$ 道测验后所有参赛者获得的硬币数量。

输入格式

第一行包含两个数字 $N$ 和 $Q$，其中 $N$ 是参赛者人数（$1 \le N \le 10^5$），$Q$ 是测验题数量（$1 \le Q \le 10^5$）。接下来的 $Q$ 行中，第 $i$ 行包含两个整数 $a_i$ 和 $p_i$，表示第 $i$ 道测验由参赛者 $a_i$ 回答（$1 \le a_i \le N$），第 $i$ 道测验的得分为 $p_i$（$-10^9 \le p_i \le 10^9$）。

输出格式

输出 $N$ 行，第 $j$ 行表示第 $j$ 位参赛者在所有 $Q$ 道测验结束后获得的硬币总数。

样例

样例输入 1

3 7
2 -1
1 4
2 5
3 6
1 -7
3 -6
2 9

样例输出 1

2
6
5

样例输入 2

9 5
2 10
2 -20
2 20
2 -20
2 20

样例输出 2

5
32
5
5
5
5
5
5
5

样例输入 3

5 10
1 0
3 0
2 0
5 0
4 0
1 0
3 0
2 0
5 0
4 0

样例输出 3

0
0
0
0
0