由于XDOJ评测机的一些奇怪行为，本题时限调整到8s。

lx正在写一个内存分配器，支持下列操作：

（1） malloc(size)，分配一个大小为size字节的内存块，返回指向该内存块的指针。

（2） free(p)，释放起始地址是p的内存块。

lx使用的分配策略是：每次找出一段地址最低的，大小不小于size字节的未分配内存，然后把这段内存的前size字节分配出来，剩余的部分仍然是未分配内存。在释放内存时，把被释放的内存块和前后的未分配内存合并成一块更大的未分配内存。

这时lw告诉lx，该分配器可能运行缓慢，并且产生大量内存碎片。lx承认了前一点，但是对于后一点十分不服气。于是，lw决定模拟该分配器的行为以证明这一点。但是，这个分配器太慢了，因此lw需要用一个较快的方法模拟该分配器的行为。

假设分配器管理的内存地址从1开始，即可供分配的内存是[1,n]。

多组数据（最多5组）。

每组数据，第一行，两个整数n、q，表示分配器管理的内存大小和操作的个数。
之后q行，每行是malloc(size)或free(p)，含义如题目描述所述。

数据保证：1<=n<=10⁹，1<=q<=100000，1<=size<=n，p是之前已经分配的某个内存块的起始地址。

对于每次malloc操作输出1行，若操作成功，输出分配的内存块的起始地址（十进制）。若分配失败，输出0。

对于第二组样例，在第6次操作后，已经分配的内存块是[2,2]和[4,4]，空闲内存块是[1,1]、[3,3]和[5,5]。它们的大小都小于2，因此分配失败。