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

附加文件

题目描述

为了保卫某秘密基地，指挥官在基地周围设置了 M 个哨岗，顺时针编号为 1 至 M，哨岗 1 和哨岗 2相邻，哨岗 2 与哨岗 3 相邻，……，哨岗 M 与哨岗 1 相邻。同时派出了 N 名哨兵负责巡逻。每名哨兵有一个巡逻区间，第 i 名哨兵的巡逻区间为 [Si, Ti]，表示从哨岗 Si 沿顺时针到哨岗 Ti 之间的范围都可以被巡逻到。任意一名哨兵的巡逻区间不会被其他哨兵的巡逻区间所完全包含。

现在，基地指挥官想知道，对于每一名哨兵，在他必须参与巡逻的前提下，至少需要多少名哨兵，才能使得他们的巡逻区间可以覆盖整个基地周围的每一寸土地？ 注：参与巡逻的士兵的巡逻区间的并形成一个封闭的环形，可以覆盖整个基地的周围，而不是只覆盖所有哨岗。

输入格式

第一行，两个正整数 $N,M$。

接下来 $N$ 行，每行两个正整数 $S_i$、$T_i$。数据保证所有哨兵的巡逻区间可以涵盖整个基地周围。

输出格式

一行，包含 $N$ 个正整数，数与数之间以一个空格隔开。其中，第 $i$ 个数表示 $i$ 号哨兵必须参加巡逻的前提下至少需要多少名哨兵才能巡逻到整个基地周围。

样例输入

4 8
2 5
4 7
6 1
7 3

样例输出

3 3 4 3

数据范围

$40$% 的数据：$N ≤ 2×10^3,M ≤ 5×10^3$。

$100$% 的数据：$N ≤ 2×10^5,M < 10^9,1 ≤ S_i,T_i ≤ M$。