Impractically Complicated Products Corporation 的工厂拥有许多生产线，以及相同数量的对应储藏室。工厂铺设了相同数量的平行传送带，用于将货物直接从生产线输送到对应的储藏室。现在，他们计划在相邻的传送带之间安装若干机械臂，以便货物可以在两条传送带之间进行拾取和放置，反之亦然。这使得来自不同生产线的货物能够被混合输送到各个储藏室。

根据机械臂的位置，来自每条生产线的货物只能被输送到部分储藏室。给定传送带的数量和机械臂的位置，你的任务是计算每间储藏室可以接收来自多少条生产线的货物。

输入格式

输入包含一组测试数据，格式如下：

$n$ $m$ $x_1$ $y_1$ $\vdots$ $x_m$ $y_m$

第一行包含一个整数 $n$ ($2 \le n \le 200000$)，表示传送带的数量。传送带编号为 $1$ 到 $n$，编号相差 $1$ 的两条传送带相邻。所有传送带均从 $x = 0$ 位置开始，到 $x = 100000$ 位置结束。另一个整数 $m$ ($1 \le m < 100000$) 是机械臂的数量。

接下来的 $m$ 行通过两个整数 $x_i$ ($0 < x_i < 100000$) 和 $y_i$ ($1 \le y_i < n$) 指示机械臂的位置。其中 $x_i$ 是第 $i$ 个机械臂的 $x$ 坐标，它可以在 $x = x_i$ 位置拾取传送带 $y_i$ 或 $y_i + 1$ 上的货物，并在同一 $x$ 坐标处将其放置到另一条传送带上。

你可以假设任意两个机械臂的 $x$ 坐标都不相同，即对于任意 $i \neq j$，都有 $x_i \neq x_j$。

图 C.1. 样例输入 1 的示意图

输出格式

在一行中输出 $n$ 个整数，以空格分隔。第 $i$ 个整数表示连接到传送带 $i$ 的储藏室可以接收来自多少条生产线的货物。

样例

样例输入 1

4 3
1000 1
2000 2
3000 3

样例输出 1

2 3 4 4

样例输入 2

4 3
1 1
3 2
2 3

样例输出 2

2 4 4 2