预订舱位

意识迷宫的入口房间里，墙壁上嵌满了全息投影——不是画面，是数据结构的实时可视化。第一个投影显示的是一个酒店预订系统：无数个房间，每个房间有一个入住时间和退房时间，需要判断能不能安排下所有预订。

"用分层台账。"你说，"每个预订是一个时间段，查询某个时刻有多少个预订重叠。"

"咋个维护？"CC问。

"建一本分层名册。"你说，"入住时在该时间段加一，退房时减一。查询某个时刻的重叠数，如果超过房间总数，就安排不下。"

你开始写。先把所有时间编号——因为时间可能很分散，但事件不多。然后建一本分层名册，每个节点维护区间内的最大重叠数。入住时，在对应区间加一；退房时，减一。查询时，看最大值是否超过容量。

屏幕上跳出了结果。第47号时间段，重叠数达到上限。

"又是47。"CC说。

"那个时间段……"Echo说，"是我叛逃的时间。Zero在那个时间点，把所有的监控都集中在了我身上。"

题目描述

$n$ 个预订，每个有入住时间和退房时间。判断能否安排下所有预订（同一时刻最多 $k$ 个重叠）。

输入格式

$n, k$。然后 $n$ 行，每行入住和退房时间。

输出格式

能否安排下所有预订。

输入样例

10 6
1 3
1 3
1 3
1 3
2 5 5
1 6

输出样例

1
4
7
0
5

提示

• 离散化时间，线段树维护区间最大重叠数。
• 入住时+1，退房时-1。
• 查询最大值是否超过 $k$。

第二个投影显示的是一幅巨大的画卷——不是纸质的，是光构成的。画卷上有无数条线段，每条线段代表一个事件的持续时间。有些线段重叠，有些不重叠。需要计算这些线段覆盖的总面积。

"铺卷尺。"你说，"把所有线段的上下边提取出来，按高度排序。从上到下扫，维护当前水平方向上被覆盖的长度。"

"又是铺卷尺？"CC问。

"对。但这次是二维的。"你说，"每个矩形有上下两条边。遇到下边就加一层，遇到上边就减一层。分层名册维护每个高度区间被覆盖的次数和实际长度。"