A: Drive

You recently landed a flashy new job at a leading tech company, and with your programming abilities rose quickly to the position of executive director of hardware procurement. Much to everyone's surprise, within the first week of your new job you managed to blow the entire hardware budget on fitting the servers with RGB capabilities. While this has made the servers look incredibly cool, it also means that you will have to downgrade the servers slightly to accommodate these unforeseen costs. You will have to use a series of floppy disks instead of a hard drive to run the server (please be reassured that this problem can be solved without knowing anything about floppy disks). Luckily, you are using the latest floppy disk technology and can store a whopping 1,474,560 bytes = 1.44 MB* on each floppy disk.

You will need to write a program to manage users creating, modifying, and destroying files. Files will be numbered in order of creation starting from $1$. The floppy disks are numbered from $1$ to $M$, and each floppy disk can either be used or free at any time.

A newly created file needs to be placed on the lowest contiguous range of free disks, which will then become used. Deleting a file simply involves marking every disk that the file occupied as free. When a file is modified, if there are enough contiguous free disks immediately after the end of the file, then the file will be shortened or extended as necessary (and disks will be marked used or free as needed) and will remain on the same first disk. Otherwise the file will be moved as if it was deleted and then recreated, but it will retain its file ID. Occasionally to make your life easier you will optimise the file layout on the floppy disks, which will involve possibly moving files such that the current order of the files is maintained but there are no free disks before any file (on a lower numbered disk compared to any file).

Input

The first line will contain two integers $N$ and $M$: the number of events you need to process, and the number of floppy disks. The following $N$ lines describe the events and have one of the following forms:

$C \space y$: create a new file with $y$ bytes

$D \space x$: destroy file $x$

$M \space x \space y$: modify file $x$, after which it will be $y$ bytes

$O$: optimise the disk layout

Output

Output a total of $N$ lines each with a single integer.

For $C$ or $M$ type events output the first disk that the file is stored on after processing the event. For $D$ type events output the first disk that the file was stored on before deletion. For $O$ type events output the difference between the number of the highest occupied disk before and after optimisation.

Constraints

• $1 \le N, M \le 100,000$
• There will be sufficient free disks to process all events: specifically file creation and modification will never fail due to insufficient disks.
• Any file that is deleted or modified will refer to a valid file that currently exists.
• The size in bytes of any file is guaranteed to fit into a 64-bit signed integer type.

Subtasks

• Subtask 1 (15%): There are only $C$ and $O$ type events.
• Subtask 2 (20%): $N \le 10,000$ and $M \le 100$
• Subtask 3 (20%): $N \le 25,000$ and there are at most $2,000$ files on the disks at any given point.
• Subtask 4 (20%): There are no $O$ type events.
• Subtask 5 (22%): There are at most $10$ $O$ type events.
• Subtask 6 (3%): No additional constraints. Warning: This subtask is unfairly difficult and anyone that manages to solve it in contest will be rewarded +1 brownie point. It is advised to only attempt this subtask if you have solved every other problem and subtask in this contest.

Sample Explanation

Sample 1

The first operation creates file $1$ which requires a single disk, and so will be placed on disk $1$ which is the lowest numbered available disk. The second operation creates file $2$ which will require $2$ consecutive disks, and will be placed starting at disk $2$ since disk $1$ is already used. The third operation deletes file $1$ and marks disk $1$ as free. The fourth operation optimises the file layout, which results in file $2$ moving to occupy disks $1$ (formerly occupied by file $1$) and disk $2$, which frees up disk $3$. Before the operation the highest number occupied disk was $3$. Afterwards, it is $2$. The difference is $1$.

Note

If you are using Python and your solution is exceeding the time limit, try selecting Python 3.6 (PyPy 7.3) when submitting as this will generally make your code run faster.

If you are using a type sensitive language like C++, Java, or C then make sure to use a 64 bit integer type to avoid integer overflow.

The problem author has provided the following image for anyone that hasn't seen a floppy disk before (with a duck for scale):

*For odd historical reasons, a MB in this case refers to 2,000 sectors of 512 bytes each. The 1.44MB floppy was a design which featured 80 tracks cut into 18 sectors of 512 bytes on each of the 2 sides for a whopping total of $80 * 18 * 512 * 2 = 1,474,560$ bytes of storage.