Don't you know that at school pupils’ programming contest a new computer language has been developed. We call it D++. Generally speaking it doesn't matter if you know about it or not. But to run programs written in D++ we need a new operating system. It should be rather powerful and complex. It should work fast and have a lot of possibilities. But all this should be done in a future.
And now you are to… No. You should not devise the name for the operating system. You are to write the first module for this new OS. And of course it's the memory management module. Let's discuss how it is expected to work.
Our operating system is to allocate memory in pieces that we’ll call “blocks”. The blocks are to be numbered by integers from 1 up to N. When operating system needs more memory it makes a request to the memory management module. To process this request the memory management module should find free memory block with the least number. You may assume that there are enough blocks to process all requests.
Now we should define the meaning of words “free block”. At the moment of first request to the memory management module all blocks are considered to be free. Also a block becomes free when there were no requests to it during T minutes.
You may wonder about a notion “request to allocated blocks”. What does it mean, “request to allocated block”? The answer is simple: at any time the memory management module may be requested to access a given block. To process this request the memory management module should check if the requested block is really allocated. If it is, the request is considered to be successful and the block remains allocated for T minutes more. Otherwise the request is failed.
That's all about the algorithms of the memory management block. You are to implement them for N = 30 000 and T = 10 minutes.
Each line of input contains a request for memory block allocation or memory block access. Memory allocation request has a form:
where <Time> is a nonnegative integer number not greater than 65 000. Time is given in seconds. Memory block access request has a form:
where <Time> meets conditions mentioned above for the memory allocation request and <BlockNo> is an integer value in range from 1 to N. There will be no more than 80000 requests.
For each line of input you should print exactly one line with a result of request processing. For memory allocation request you are to write an only integer — a number of allocated block. As it was mentioned above you may assume that every request can be satisfied, there will be no more than N simultaneously allocated blocks. For memory block access request you should print the only character:
- '+' if request is successful (i.e. block is really allocated);
- '-' if request fails (i.e. block with number given is free, so it can't be accessed).
Requests are arranged by their times in an increasing order. Requests with equal times should be processed as they appear in input.
2 . 2
2 . 3
3 . 30000
601 . 1
601 . 2
602 . 3
1202 . 2
Problem Author: Alexander Klepinin
Problem Source: Ural State University Internal Contest October'2000 Students Session