Description

The objective of the program of Quiz 3 is managing the reservation states of the rooms, where each room has a corresponding number.

This system contains two types of instructions:

• RESERVE:
  • Description: Reserve k unreserved rooms. If the number of unreserved rooms is larger than k, reserve the rooms based on the room numbers (the larger the number is, the higher priority to be reserved).  If the number of unreserved rooms is less than k, abort the operation with an error message.
  • Usage: RESERVE k
  • Parameters:
    • k: Number of rooms to reserve.
  • Example:
    • RESERVE 3: Reserve the 3 rooms (whose room numbers are the largest ones among unreserved rooms).
      • If the rooms with room number 1,3,5,7,9 have not been reserved, then the rooms with room number 5,7,9 should be reserved by this instruction.
      • If the rooms with room number 7,9 have not been reserved, then the system will abort the operation with an error message.
• UNRESERVE:
  • Description: Unreserved the rooms with the given room number. Note that if the room with the given room number is not reserved originally, the instruction will fail.
  • Usage: UNRESERVE roomNum
  • Parameters:
    • roomNum: The room number of the room that needs to be unreserved.
  • Example:
    • UNRESERVE 5: Unreserve the room with room number 5.

​​​

---

Hint

If you want to use the priority queue(heap) in STL, remember to include <queue>

If you want to use the vector in STL, remember to include <queue>

If you want to use max-heap to solve the problem, you can declare a variable as below:

priority_queue <int> pq;

If you want to use min-heap to solve the problem, you can declare a variable as below:

priority_queue <int, vector<int>, greater<int>> pq;

Input

The first line contains an integer n, representing the number of the rooms.

The room number starts from 0 to n-1. 

The second line contains an integer m, representing the number of instructions.

Each line starts with a string  Si, representing the type of instructions.

Si will be one of the following tokens: RESERVE, UNRESERVE.

If Si is RESERVE, it will be followed by a parameter k. k is an integer that represents the number of rooms to reserve.

 

If Si  is UNRESERVE, it will be followed by a parameter roomNum. roomNum is an integer that represents the room number of the room that needs to be unreserved.

It is guaranteed that:

0 < n, k ≤ 10³

0 ≤ roomNum < 10³

0 < m ≤ 10⁶

Output

The output of RESERVE:

• If successfully reserving the room, the output is: "RESERVE: reserve room roomList".
  • roomList is a string that represents a sequence of room numbers from the largest to the smallest separated by ",".
• If reserving the room fails, "RESERVE: no vacant rooms" should be the output.

The output of UNRESERVE:

• If the room is unreserved successfully, "UNRESERVE: unreserved room roomNum" should be the output. roomNum represents the room number of the room that needs to be unreserved.
• If unreserve the room fails, the output is "UNRESERVE: roomNum has not been reserved". roomNum represents the room number of the room that needs to be unreserved.

A new line is required at the end of each instruction output.

Sample Input  Download

Sample Output  Download

Tags

Discuss