8662: BZOJ4662:Snow

Memory Limit:256 MB Time Limit:4 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

2333年的某一天,临冬突降大雪,主干道已经被雪覆盖不能使用。城 主 囧·雪 决定要对主干道进行一次清扫。 临冬城的主干道可以看为一条数轴。囧·雪 一共找来了n个清理工,第 i个清理工的工作范围为[li,ri],也就是说这个清理工会把[li,ri]这一 段主干道清理干净(当然已经被清理过的部分就被忽略了)。当然有可能主 干道不能全部被清理干净,不过这也没啥关系。 虽然 囧·雪 啥都不知道,但是他还是保证了不会出现某一个清理工的 工作范围被另一个清理工完全包含的情况(不然就太蠢了)。 作为临冬城主,囧·雪 给出了如下的清扫方案: 在每一天开始的时候,每一个还没有工作过的清理工会观察自己工作 范围内的道路,并且记下工作范围内此时还没有被清理的道路的长度(称 为这个清理工的工作长度)。然后 囧·雪 会从中选择一个工作长度最小的 清理工(如果两个清理工工作长度相同,那么就选择编号小的清理工)。然 后被选择的这个清理工会清理自己的工作范围内的道路。为了方便检查工 作质量,囧·雪 希望每一天只有一个清理工在工作。 你要注意,清理工的工作长度是可能改变的,甚至有可能变成0。尽管 如此,这个清理工也还是会在某一天工作。 现在,囧·雪 想要知道每一天都是哪个清理工在工作?


输入格式

第一行两个整数t,n。分别表示主干道的长度(也就是说,主干道是数 轴上[1,t]的这一段)以及清理工的人数。 接下来n行,每行两个整数li,ri。意义如题。 n<=3*10^5, 1<=li<ri<=t<=10^9,保证输入的li严格递增


输出格式

输出n行,第i行表示第i天工作的清理工的编号。


样例输入

15 4
1 6
3 7
6 11
10 14

样例输出

2
1
3
4

提示

没有写明提示


题目来源

没有写明来源

加入题单

上一题 下一题 算法标签: