ДОРЕШИВАНИЕ 2014 ACM-ICPC Украина, 2ой Раунд Украина, Сентябрь 13

Memory Manager

You are working on the compiler of your own brand new programming language and you have already implemented everything except for memory manager (MM). MM is responsible for allocating objects in memory and deleting them when they become unnecessary. In total, there are n consecutive bytes of memory in your computer. Each object requires certain amount of consecutive bytes in memory. During its execution, the program can send queries of two types to MM:

1) Allocate an object of size a bytes. Note that this size can be different for different objects. Two objects cannot have shared memory.

2) Remove the given object, which was previously allocated.

You know in advance all m queries, which will be sent to MM. Find the way to process them all or report that it is impossible. It is guaranteed that there will be not more than two queries of the second kind.


The first line of the input contains two integers n and m (1n105, 1m105). Each of the next m lines contains two integers a and b. If a = 1, then b is equal to the size of an object you need to allocate. If a = 2, then b is equal to the index of query which was already processed and means that you should remove an object allocated in that query. It’s guaranteed that the input is correct, e.g. you’ll never be asked to remove an already removed object, etc.


If it is impossible to perform all queries, print one line with the word “IMPOSSIBLE” (without quotes). Otherwise, for each query of the first type (the ones with a = 1) you should output one number in its own line, which represents the position of the first byte of an allocated object.Bytes in memory are numbered from 0. If there are several valid answer sequences, you may output any of them.

Time limit 1 second
Memory limit 64 MiB
Input example #1
10 5
1 5
1 5
2 2
1 5
2 1
Output example #1
Source 2014 ACM-ICPC Ukraine, 2nd Round Ukraine, September 13, Problem E