国旗计划

• 时间限制：1.5 秒
• 内存限制：256 MiB

题目描述

A 国正在开展国旗计划：多名边防战士以接力形式手举国旗环绕边境线一圈。

边境线上设有 $M$ 个边防站，顺时针编号 $1$ 至 $M$。第 $i$ 名战士常驻 $C_i,D_i$ 两个边防站，能够从 $C_i$ 沿顺时针方向奔袭至 $D_i$，这段路程称为他的奔袭区间。任意一名战士的奔袭区间都不会被另一名战士的奔袭区间包含。

对于每一名战士，请求出在他必须参加国旗计划的前提下，覆盖全部边境线至少需要多少名战士。

输入格式

第一行包含两个正整数 $N,M$，分别表示战士数量和边防站数量。

随后 $N$ 行，每行包含两个正整数 $C_i,D_i$，表示第 $i$ 名战士的奔袭区间。数据保证所有奔袭区间能够覆盖整个边境线，且任意区间互不包含。

输出格式

输出一行，包含 $N$ 个正整数。第 $i$ 个整数表示第 $i$ 名战士必须参加时，覆盖全部边境线所需的最少战士人数。

样例输入 1

4 8
2 5
4 7
6 1
7 3

样例输出 1

3 3 4 3

数据范围

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