题目描述

学校正在开展一项特殊的长跑接力比赛，比赛规则是学生们拿着交接棒通过接力的方式绕着赛道跑一圈，学校已经选好了 $n$ 名学生作为候选人。

但这个接力要求比较特殊，首先跑道上会有 $m$ 个站点，按照跑道顺时针方向编号为 $1$ 到 $m$ ，每名学生会有两个规定的站点，并只能在这两个站点之间折返跑，规则规定这个折返跑区间称为学生的覆盖区间。因为要覆盖完跑道，所以学校给每名学生分配的覆盖区间不会相互包含。

现在学校想知道，对于每个学生 $i(i \in [1,n])$ ，假设他必须参与，那么至少还需要在候选人里面选多少个学生，才能完全覆盖跑道。

输入格式

第一行，包含两个正整数 $n,m$，分别表示学生数量和站点数量。

接下来 $n$ 行，每行包含两个正整数 $c_i$、$d_i$ ，分别表示 $i$ 号学生两个站点编号，$c_i$ 号站点沿顺时针方向至 $d_i$ 号站点是他的覆盖区间。

输出格式

输出数据仅 $1$ 行，需要包含 $n$ 个正整数。其中，第 $j$ 个正整数表示 $j$ 号学生必须参加的前提下至少需要多少名学生才能完全覆盖跑道。

样例 #1

样例输入 #1

4 8
2 5
4 7
6 1
7 3

样例输出 #1

3 3 4 3

数据范围

$N\leqslant 2×10^5,M<10^9,1\leqslant C_i,D_i\leqslant M$。

数据保证整个跑道都是可被覆盖的。