Under construction

Still being built. Things may change

Super Cheap Party Rooms

Interview

Time limit1sMemory limit512 MB

Summary
Manage a row of N rooms across new/in/out queries, placing each new room in the leftmost gap of size Y and cleaning it when its guests leave.
Level

Medium7 of 10

Topics
Intervals, Simulation, Sorting, Binary search
Solved
No attempts yet

Problem

Pilgi, who loves to play, turned out to be the second-generation heir of a conglomerate. So he is starting a new kind of party room business. This business aims to provide guests with rooms of whatever size they want, for however long they want. Pilgi bought an abandoned school and remodeled the building into a rectangular box shape. He then put up light temporary walls to remodel it into a row of N consecutive rooms, each 1 pyeong in size. Each room is numbered 1 to N from left to right.

Whenever a guest arrives, Pilgi asks for the number of people X and the desired size in pyeong Y. He then finds Y consecutive empty rooms, removes the walls between them, and makes them into a single room of Y pyeong to give to the guest. To make management easier, Pilgi wants to make the new party room as far to the left as possible. (He wants to assign it to the location with the lowest possible room numbers.)

Additional guests can enter a room that is in use, and some guests may check out. When all guests in a room have checked out, Pilgi cleans the room and reinstalls the walls he removed. That room is split back into the original consecutive 1-pyeong rooms and can be assigned to a new guest.

An assigned room can be described by the number L of its leftmost room and the number R of its rightmost room. When told to output "L R", output the leftmost and rightmost room numbers of the assigned room.

Pilgi must handle the following 3 kinds of operations. Every number in an operation is an integer.

  • new X Y (1 ≤ X ≤ 2,147,483,647, 1 ≤ Y ≤ N): X guests want a party room of Y pyeong. If a new party room of Y pyeong can be made, assign a new room and output "L R". If it is impossible, output "REJECTED" and turn the guest away.
  • in A B (1 ≤ B): B more guests enter the party room assigned as the A-th assignment in chronological order. The room assigned as the A-th assignment must be found, including rooms that have already been cleaned away. This room is currently assigned, and it is guaranteed that after the additional guests enter, the number of people in the room does not exceed 2,147,483,647. Nothing is output for this operation.
  • out A B (1 ≤ B): B guests check out of the party room assigned as the A-th assignment. It is guaranteed that more guests never check out than the number of guests in the party room. If all guests in the party room check out, output "CLEAN L R".

Pilgi has never run a business, so he asks you for help. Write a program to help Pilgi manage the building.

Input

The first line gives N and Q. (1 ≤ N, Q ≤ 5000)

Each of the following Q lines gives one of the three kinds of operations.

Output

For each query, output the appropriate answer.

Hint

Examples3

  1. Example 1

    Input
    4 6
new 4 1
new 4 2
in 1 1
out 2 4
new 4 3
out 1 5
    Expected output
    1 1
2 3
CLEAN 2 3
2 4
CLEAN 1 1

  2. Example 2

    Input
    4 4
new 4 1
new 4 4
new 3 3
out 2 3
    Expected output
    1 1
REJECTED
2 4
CLEAN 2 4

  3. Example 3

    Input
    6 6
new 4 1
new 4 2
in 1 1
new 4 3
out 2 4
new 4 2
    Expected output
    1 1
2 3
4 6
CLEAN 2 3
2 3