U140358 操作系统

操作系统($Operating\ System$，简称$OS$)是管理计算机硬件与软件资源的计算机程序。操作系统需要处理如管理与配置内存、决定系统资源供需的优先次序、控制输入设备与输出设备、操作网络与管理文件系统等基本事务。操作系统也提供一个让用户与系统交互的操作界面。 操作系统主要包括以下几个方面的功能 ： ①进程管理，其工作主要是进程调度，在单用户单任务的情况下，处理器仅为一个用户的一个任务所独占， 进程管理的工作十分简单。但在多道程序或多用户的情况 下，组织多个作业或任务时，就要解决处理器的调度、 分配和回收等问题 。 ②存储管理分为几种功能：存储分配、存储共享、存储保护 、存储扩张。 ③设备管理分有以下功能：设备分配、设备传输控制 、设备独立性。 ④文件管理：文件存储空间的管理、目录管理 、文件操作管理、文件保护。 ⑤作业管理是负责处理用户提交的任何要求。 现在，$Seaway$自己尝试着开发了一套操作系统$Seaway-Andr$。但是由于$Seaway$水平有限，其上述部分功能并没有完善，其中bug最多的就是其内存管理系统。 在$Seaway$的开发计划里，$Seaway-Andr$的第一版内存管理系统是这样的： 1、`new n`：在内存中分配$n$字节的空间。此命令将返回已分配的内存块的编号$x$。 在$Seaway$的开发计划中，对`new`操作的说明是这样的： 操作$new$有一个参数$n$，表示需要分配$n$字节大小的内存块。在执行这个操作时，系统将把一块最靠近内存起点的，长度为$n$的**连续空闲字节**分配到一个内存块（这块内存块内的所有字节将被标记为“已使用”）。这个操作的返回值为这块内存块的编号。如果没有符合条件的内存块，返回$NULL$。 2、`delete x`：释放编号为$x$的内存块。 在$Seaway$的开发计划中，对`delete`操作的说明是这样的： 操作$delete$有一个参数$x$，表示需要释放的内存块的编号。它将释放这个内存块（这块内存块内的所有字节将被标记为“空闲”）。如果成功释放，不返回值；如果编号为$x$的内存块不存在，返回$ILLEGAL\_DELETE\_ARGUMENT$。 3、`zhengli`：碎片整理，将所有内存块全部向内存的起点靠拢并且不改变它们的顺序。 在$Seaway$的开发计划中，对`zhengli`操作的说明是这样的： 操作$zhengli$没有任何参数。它只是将所有内存块向前依次（编号小的地方）挪动直到它们紧挨在一起。**（不改变它们的顺序） ** 可以看出，这个内存管理系统是**简单线性**的。在这个内存管理系统中，整个内存条有$m$个字节，依次从$1-m$编号。 那么，现在$Seaway$许下了丰厚的报酬（本题$100pts$）来请你做他的内存管理系统测试员。这是你的工作指南： 你将用**连续的正整数**（1,2,...）作为每一个内存块的编号。比如，第$i$次分配的内存块编号为$i$。你的任务是：依次输出所有`new`指令的返回值，以及所有执行失败的`delete`指令的返回值。

从文件$system.in$中读入数据。 第一行包括两个正整数$t$和$m$。$t$表示操作次数，$m$表示内存大小。接下来的$t$行为每一次的命令。命令有以下三种，格式均由题目描述所示：`new`命令，后接一个整数$n$；`delete`命令，后接一个整数$x$；`zhengli`命令。

输出到文件$system.out$中。 每一行依次为每次执行的`new`函数的返回值或执行失败的`delete`函数返回的$ILLEGAL\_DELETE\_ARGUMENT$。

【**数据范围**】 对于$30\%$的数据，保证不存在`zhengli`操作。 对于$60\%$的数据，$1\le t,m\le 10$。 对于全部数据，有$1\le t,m\le 100$。