Description

A parking lot has n parking spaces, each with a size s_i. There are m events, which can be one of three types:

1. A car of size x wants to park.
2. A car in space y leaves.
3. Query how many parking spaces of size z are still available.

For each event of type 1 (a car entering), assign a parking space based on these rules:

1. Choose the smallest space that is >= x.
2. If multiple spaces meet rule 1, follow the driver’s preference: if they prefer "small," assign the space with the smallest number; if they prefer "big," assign the space with the largest number.
3. If no space meets rule 1, skip the operation and don’t assign a space.

For each car entering operation, output the assigned parking space number. If no space can be assigned, output -1.

Input

The first line contains two positive integers n and m, representing the number of parking spaces and the number of events, respectively.
The second line contains n positive integers s₁ ~ s_n, representing the size of each parking space.
The next m lines each describe an event in one of three formats:
1 x small/big: A car of size x with a preference for small (smallest numbered space) or big (largest numbered space) wants to park.
2 y: The car in parking space y leaves the parking lot.
3 z: Query how many parking spaces of size z are still available.

Constraints

• 1 <= n, m <= 200000
• 1 <= x <= 10⁹
• 1 <= y <= n

Subtasks

• Testcases 1, 2: There will only be type 1 events (cars entering).
• Testcases 3, 4: Each car's preference will only be "small" (choosing the smallest numbered parking space).
• Testcases 5, 6: Each car's preference will only be "big" (choosing the largest numbered parking space).
• Testcases 7, 8 No additional constraints.

Output

For each car entering event, output the assigned parking space number, or -1 if no space can be assigned. For each query event, output the corresponding answer.

Sample Input  Download

Sample Output  Download

Tags

Discuss