Problem 1116. -- 内存管理

1116: 内存管理

Time Limit: 1 Sec  Memory Limit: 512 MB
Submit: 95  Solved: 27
[Submit][Status][Web Board]

Description

在公元2018年4月21日的凌晨,张老师做了一个神奇的梦!在梦里,张老师变成了比赛评测机的内存管理员。在评测机里面一共有N块够任何程序使用的内存块,内存块的编号从0开始,一直到N-1。尽管这是在张老师的梦里,但是张老师竟然被人压迫了!张老师收到了辛格尔神的命令,要求当有程序申请内存时,张老师必须每次从可用的内存块里找出编号最小的给程序使用。好心的辛格尔神的女儿事先告诉了张老师一共有多少个程序将会申请内存。但是在梦里的张老师依旧是没有空的,所以想让你帮他写个程序搞定这件事情。

Input

题目包含多组数据。
第一行一个整数T,表示有T组测试数据。(1 ≤ T2)
对于每组数据分为M+2行:
第一行有一个整数N,表示张老师一共管理N块内存;(N100000)
第二行有一个整数M,表示一共将会有M个申请内存的请求。(M100000)
接下来M行,每行两个整数startI 和timei,表示在startI有一个使用时间为timei的请求。
对于0 < i < N, 保证starti  starti+1,并且starti+1 - starti ≤ 2000
对于0 < iN, 保证0 < timei 108

Output

对于每组数据,第一行输出Case #x: (x编号从1开始)
对于每组数据,一共输出M行,表示M个请求时,张老师所给分配的内存编号,如果某次请求时,没有
空闲内存,则该次请求输出"no space left"。

Sample Input

2
5
5
1 2
1 1
3 3
4 1
6 2
10
10
2 4
6 3
8 5
11 2
13 1
13 2
15 1
15 4
19 2
21 5

Sample Output

Case #1:
0
1
0
1
0
Case #2:
0
0
1
0
0
1
0
1
0
0

HINT

Source

[Submit][Status]