该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

落落计划在一条长度为 $n$ 的道路旁种植一排树，路的位置编号从 $1$ 到 $n$。

在接下来的 $m$ 次操作中，落落会选择一个区间 $[l,r]$，并在该区间内的每个位置种植树木。具体来说，在位置 $i \ (l \leq i \leq r)$ 种植的树木数量为 $i-l+1$ 棵树。

经过所有操作后，您需要告诉落落每个位置上种植了多少棵树。

输入格式

输入的第一行包含两个正整数 $n,m$，分别表示道路的长度和种树操作的次数。

接下来的 $m$ 行，每行包含两个正整数 $l_{i},r_{i} \ (1\leq l_{i} \leq r_{i} \leq n)$，表示每次种树的区间。

输出格式

请输出一行包含 $n$ 个整数，表示道路上每个位置处种植的树木数量。

样例 1

输入

6 2
1 6
3 6

输出

1 2 4 6 8 10

样例 2

输入

5 2
2 4
1 3

输出

1 3 5 3 0

样例 3

见下发文件tree3.in/out.

数据范围

对于 $30\%$ 的数据 ，保证 $n \le 10^{3} ,m \le 10^{3}$ 。

对于 $70\%$ 的数据，保证 $n \le 10^{4} ,m \le 10^{4}$ 。

对于 $100\%$ 的数据，保证 $n \le 2 \times 10^{5} ,m \le 2 \times 10^{5}$ 。