题目描述

安迪在他的庄园里种了 $n$ 棵树，排列成一排，标号为 $1$ 到 $n$。最开始的时候 $n$ 棵树的高度都是 $0$，也就是种子刚刚被埋下，树还没有长出来。安迪会一种魔法，他每使用一次魔法，就可以让树标号落在连续区间 [$l$, $r$] 里的树的高度增加 $1$。他可以使用 $q$ 次这种魔法，然后他很好奇，在使用了 $q$ 次魔法之后，他的所有树的高度分别是多少呢？

输入格式

第一行输入两个整数 $n$，$q$ ( $1 \le n,q \le 10^5$ )。

接下来 $q$ 行，每行输入两个整数 $l$, $r$，表示安迪让标号落在区间 [$l$, $r$] 里的树高度都加 $1$。($1 \le l \le r \le n$)

输出格式

输出共一行，包含 $n$ 个整数，第 $i$ 个数表示第 $i$ 棵树的高度，每个数字后面输出一个空格。

样例

10 3
1 3
2 4
3 3

1 2 3 1 0 0 0 0 0 0