Under construction

Still being built. Things may change

Hotel Rooms

Interview

Time limit1sMemory limit1024 MB

Summary
Given n hotel rooms and a list of reservations, the task is to answer how many rooms in each queried range are still free.
Level

Easy3 of 10

Topics
Segment tree, Array
Solved
No attempts yet

Problem

When the UCF Programming Team travels, the coaches would like to get hotel rooms that are close to each other. There is a hotel where rooms are numbered 1 through n, and these rooms are in a straight line. Room 2 is next to Room 1, Room 3 is next to Room 2, and so on. So, it is easier to find a large number of available rooms that are close to each other.

Given the room reservations, determine the availability of rooms to accommodate the UCF Programming Team (a large group).

Input

The first line contains two integers: nn (1≤n≤5×1051 \le n \le 5 \times 10^5), the number of hotel rooms, and tt (1≤t≤1051 \le t \le 10^5), the number of transactions. Each of the next tt lines contains one transaction. There are two types of transactions:

  • Room Reservation: the line starts with the letter R, followed by one space and a valid room number. This transaction reserves the given room. The room is not already reserved.
  • Group Room Availability: the line starts with the letter A, followed by one space, a valid starting room number, one space, and a valid ending room number. This transaction asks how many rooms are available in the given range. The ending room number is not less than the starting room number.

Output

There is no output for the room-reservation transactions. For each group room availability transaction, output a separate line with the total number of available rooms in the requested range.

Examples1

  1. Example 1

    Input
    20 8
A 5 10
R 6
R 9
R 3
A 5 10
R 13
R 18
A 1 20
    Expected output
    6
4
15