威廉在伦敦市中心拥有一套公寓。他决定在接下来的 $$$n$$$ 天内出租他的公寓来赚点钱。
由于他的公寓位于市中心,因此他立即收到了 $$$m$$$ 的报价,格式为 $$$(l_i, r_i)$$$,这意味着有人想要预订从 $$$l_i$$$ 到 $$$r_i$$$ 期间的公寓。为了避免花费大量时间来弄清楚接受报价对他是否有利可图,威廉决定开发一种算法。该算法会在所有报价到达时对其进行处理,并且仅在满足以下两个条件时才接受报价 $$$i$$$:
- $$$r_i - l_i + 1 \ge x$$$。
- $$$l_i$$$ 和 $$$r_i$$$ 之间没有任何天被先前接受的报价占用
William 不确定 $$$x$$$ 应该有什么值,他向你寻求帮助。对于从 $$$1$$$ 到 $$$n$$$ 的所有 $$$x$$$,如果将相应的值分配给 $$$x$$$,他希望您计算该公寓将被占用的总天数。
输入
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ $$$(1 \le n \le 5 \cdot 10^4, 1 \le m \le 10^5)$$$,分别是天数和优惠数。
接下来的 $$$m$$$ 行包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ $$$(1 \le l_i \le r_i \le n)$$$,描述第 $$$i$$$ 个租赁报价。所有优惠均按时间顺序排列。
输出
打印 $$$n$$$ 整数。如果算法使用等于 $$$i$$$ 的 $$$x$$$ 值,则 $$$i$$$ 行中的数字必须等于公寓将被占用的天数。
示例
输入 #1
6 5 2 3 3 5 1 1 1 5 1 6
输出 #1
3 2 3 5 5 6
注意
每个 $$$x$$$ 的第一个样本测试的段描述:
- $$$x = 1$$$ — 算法将批准报价:$$$1$$$ (2..3)、$$$3$$$ (1..1)。 William 的公寓总共出租天数为 3 天
- $$$x = 2$$$ — 算法将批准报价:$$$1$$$ (2..3)。 William 公寓的出租总天数为 2
- $$$x = 3$$$ — 算法将批准报价:$$$2$$$ (3..5)。 William 的公寓总共出租天数为 3 天
- $$$x = 4$$$ — 算法将批准报价:$$$4$$$ (1..5)。 William 公寓的出租总天数为 5
- $$$x = 5$$$ — 算法将批准报价:$$$4$$$ (1..5)。 William 公寓的出租总天数为 5
- $$$x = 6$$$ — 算法将批准报价:$$$5$$$ (1..6)。 William 的公寓总共出租天数为 6 天