Trapped Soldier

In a county there are n houses connected in a tunnel in a line; house i is only connected to house i-1 and house i+1. Initially, all houses are intact, and a soldier in any house can travel freely to all other houses.

However, a series of m messages arrive. There are three types of messages:

• D x: The enemy destroys house x and blocks its tunnel. A destroyed house is no longer accessible.
• R: The villagers repair the most recently destroyed house (i.e. the last house destroyed that hasn’t yet been repaired).
• Q x: A query indicating that a soldier is trapped in house x. The soldier can only use tunnels connecting intact houses. The question is: how many houses can the soldier reach (including house x)?

Mathematically, if the soldier is in house x and that house is in a contiguous segment of intact houses from L to R, then his reachable houses count is given by:

Your task is to process the m messages in order, and for every query message output the number of houses in the connected segment containing house x.

inputFormat

The first line contains two integers n and m (1 ≤ n, m ≤ 10⁵), representing the number of houses and the number of messages.

Then follow m lines, each representing a message. The messages are in one of the following forms:

• D x (1 ≤ x ≤ n): Destroy house x.
• R: Repair the most recently destroyed house that has not been repaired yet.
• Q x (1 ≤ x ≤ n): Query the number of houses reachable from house x.

It is guaranteed that every repair operation corresponds to a previous destroy operation.

outputFormat

For each query operation, output a single line containing one integer — the number of houses reachable from the queried house.

sample

6 7
Q 3
D 3
Q 2
D 1
Q 2
R
Q 2

6
2
1
2