Bullmoose Hotel Room Assignment

The Bullmoose Hotel has n rooms in a long corridor. Visitors arrive in groups, and each group requests a block of contiguous empty rooms. For a check‐in request, assign the smallest possible block of x contiguous empty rooms. If such a block is available, the rooms are filled and the leftmost room number is output; otherwise, output 0 indicating that no suitable block exists.

There is also a checkout operation, which frees a consecutive block of rooms. Note that a checkout may free rooms that are already empty. Initially, all rooms are empty.

Formally, you are given two integers n and m where n (1 \(\leq n \leq 50000\)) denotes the number of rooms (numbered from 1 to n) and m (1 \(\leq m < 50000\)) the number of operations. Each of the next m lines contains an operation:

• Check-in (operation type 1): The line contains "1 x" where x (1 \(\leq x \leq n\)) is the number of consecutive rooms requested. Find the smallest room number r such that the rooms numbered \(r, r+1, \ldots, r+x-1\) are all empty. If such a block exists, assign these rooms (i.e. mark them as occupied) and output r; otherwise, output 0.
• Checkout (operation type 2): The line contains "2 x y" where x and y specify that the rooms numbered \(x, x+1, \ldots, x+y-1\) become empty.

Your task is to process all operations in order and output the result for each check-in request. All formulas are given in \(\LaTeX\) format, for example, the range of rooms for a check-in is given as \(r, r+1, \dots, r+x-1\).

inputFormat

The first line contains two integers n and m, where n is the number of rooms (1 \(\leq n \leq 50000\)) and m is the number of operations (1 \(\leq m < 50000\)). Each of the following m lines describes an operation in one of the following formats:

• Check-in: A line starting with "1" followed by an integer x (1 \(\leq x \leq n\)).
• Checkout: A line starting with "2" followed by two integers x and y where 1 \(\leq x \leq n-y+1\); this operation frees the rooms \(x, x+1, \dots, x+y-1\).

outputFormat

For each check-in operation (operation type 1), output a single line containing the starting room number of the allocated block, or 0 if no block of x contiguous empty rooms is available.

sample

10 6
1 3
1 3
1 3
2 4 3
1 3
1 3

1
4
0
4
0