题目描述

某国正在实施一项边境巡逻计划。巡逻队需要沿国境线接力奔跑一整圈，这需要多名队员协同完成。参谋部已经选拔了 $N$ 名精英队员作为候选人。

国境线上设有 $M$ 个检查站，沿顺时针编号 $1$ 至 $M$。每名队员负责两个检查站之间的路段，我们称这个路段为他的巡逻区间。$N$ 名队员都是精挑细选的，没有任何一名队员的巡逻区间被其他队员的巡逻区间完全包含。

参谋长希望知道，至少需要多少名队员，才能使他们的巡逻区间覆盖全部国境线。不仅如此，他还想了解：对于每一名队员，在他必须参与巡逻的前提下，至少还需要多少名队员才能覆盖全部国境线。

输入格式

第一行，包含两个正整数 $N$ 和 $M$，分别表示队员数量和检查站数量。

随后 $N$ 行，每行包含两个正整数 $C_i$、$D_i$，分别表示第 $i$ 名队员负责的两个检查站编号，从 $C_i$ 沿顺时针至 $D_i$ 为其巡逻区间。数据保证整个国境线均可被覆盖。

输出格式

输出一行，包含 $N$ 个正整数，用空格分隔。第 $j$ 个正整数表示第 $j$ 名队员必须参与的前提下至少需要多少名队员才能覆盖全部国境线。

样例

4 8
2 5
4 7
6 1
7 3

3 3 4 3

提示

$N \le 2 \times 10^5$，$M \lt 10^9$，$1 \le C_i, D_i \le M$。