Dynamic Power Strip Allocation and Query

In Xiao M's laboratory, there are n power strips numbered from \(1\) to \(n\) arranged from left to right. Every morning, all power strips start unused. Whenever a student enters the lab, he/she plugs in his/her laptop charger following a peculiar process:

1. Find the longest contiguous interval of unused power strips. If there are multiple intervals with the same maximum length, choose the rightmost interval.
2. Plug the charger into the middle power strip of that interval. If the interval length is even (so there are two "middle" positions), choose the right one. In other words, if the chosen free interval is \([l,r]\), the student occupies the power strip at position \(\left\lfloor \frac{l+r+1}{2} \right\rfloor\).

When a student leaves the lab, he/she unplugs the charger from his/her occupied power strip. It is guaranteed that whenever a student enters the lab, there is at least one free power strip.

Your task is to process a series of events and answer queries. There are three kinds of events:

• A — A student arrives and occupies a power strip using the procedure described above.
• L x — The student at power strip \(x\) leaves (i.e. the power strip \(x\) becomes free).
• Q l r — Query how many power strips are currently occupied in the interval \([l, r]\).

Input format: The first line contains two integers \(n\) and \(m\) (the number of power strips and the number of events, respectively). Each of the next \(m\) lines is in one of the formats described above.

Output format: For each query event, output a single integer indicating the number of occupied power strips in the specified interval.

inputFormat

The first line contains two integers \(n\) and \(m\) (\(1 \le n, m \le 10^5\), for example). Each of the following \(m\) lines represents an event in one of the following formats:

• A — A student arrives.
• L x — A student leaves from power strip \(x\) (\(1 \le x \le n\)).
• Q l r — Query the number of occupied power strips in the interval \([l, r]\) (\(1 \le l \le r \le n\)).

outputFormat

For each query event, output a single line with one integer: the number of occupied power strips in the range \([l, r]\).

sample

10 7
A
A
Q 1 10
A
L 6
Q 1 10
A

2
2