CF1523G.Try Booking

William owns a flat in central London. He decided to rent his flat out for the next $n$ days to earn some money.

Since his flat is in the center of the city, he instantly got $m$ offers in the form $(l_i, r_i)$, which means that someone wants to book the flat from day $l_i$ until day $r_i$ inclusive. To avoid spending a lot of time figuring out whether it's profitable for him to accept an offer, William decided to develop an algorithm. The algorithm processes all offers as they arrive and will only accept offer $i$ if the following two conditions are satisfied:

• $r_i - l_i + 1 \ge x$.
• None of the days between $l_i$ and $r_i$ are occupied by a previously accepted offer

William isn't sure what value $x$ should have and he asks you for help. For all $x$ from $1$ to $n$ he wants you to calculate the total number of days for which the flat would be occupied if the corresponding value will be assigned to $x$.

威廉在伦敦市中心拥有一套公寓。他决定将这套公寓出租 $n$ 天以赚取一些收入。

由于他的公寓地处市中心，他立刻收到了 $m$ 个预订请求，每个请求形如 $(l_i, r_i)$，表示某人希望从第 $l_i$ 天到第 $r_i$ 天（含端点）租住该公寓。为了避免花费大量时间判断接受某个请求是否盈利，威廉决定设计一个算法。该算法按请求到达的顺序依次处理所有请求，并且仅当以下两个条件同时满足时才接受第 $i$ 个请求：

• $r_i - l_i + 1 \ge x$；
• 区间 $[l_i, r_i]$ 内的任意一天均未被之前已接受的请求占用。

威廉不确定参数 $x$ 应取何值，因此向你求助。请你针对每个 $x = 1, 2, \dots, n$，计算：若将该 $x$ 值代入上述算法，则公寓总共会被占用多少天。

The first line contains two integers $n$ and $m$ $(1 \le n \le 5 \cdot 10^4, 1 \le m \le 10^5)$, which are the number of days and the number of offers, respectively.

Each of the next $m$ lines contains two integers $l_i$ and $r_i$ $(1 \le l_i \le r_i \le n)$, which describe the $i$-th renting offer. All offers are given in chronological order.

第一行包含两个整数 $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$ 个租赁报价。所有报价均按时间顺序给出。

Print $n$ integers. The number in $i$-th line must be equal to the number of days the flat would be occupied if the algorithm will use the value of $x$ equal to $i$.

输出 $n$ 个整数。第 $i$ 行的数字必须等于：当算法中 $x$ 的取值为 $i$ 时，该公寓被占用的天数。

The description of segments from the first sample test for each $x$:

• $x = 1$ — algorithm will approve offers: $1$ (2..3), $3$ (1..1). The total number of days for which William's flat will be rented out is 3
• $x = 2$ — algorithm will approve offers: $1$ (2..3). The total number of days for which William's flat will be rented out is 2
• $x = 3$ — algorithm will approve offers: $2$ (3..5). The total number of days for which William's flat will be rented out is 3
• $x = 4$ — algorithm will approve offers: $4$ (1..5). The total number of days for which William's flat will be rented out is 5
• $x = 5$ — algorithm will approve offers: $4$ (1..5). The total number of days for which William's flat will be rented out is 5
• $x = 6$ — algorithm will approve offers: $5$ (1..6). The total number of days for which William's flat will be rented out is 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