Background

Xiao Ka is watching TV in the living room of the new home. On TV, the endlessly re-run “Drawing Sword” (Liangjian) is playing. In the show, the Independent Regiment led by Li Yunlong encounters an enemy squad in a county seat, and they begin a guerrilla war.

Problem Description

There are $n$ houses in the county connected by tunnels in a line. The $i$-th house is connected only to the $(i-1)$-th and $(i+1)$-th houses. Specifically, house $1$ is connected only to house $2$, and house $n$ is connected only to house $n-1$. There are $m$ messages arriving in order:

1. If the message is D x: the enemy destroys house $x$, and the tunnel is blocked.
2. If the message is R: the villagers repair the most recently destroyed house.
3. If the message is Q x: a soldier is trapped in house $x$.

Define reachability as follows: if there exist houses $i, j$ ($1 \leq i \leq j \leq n$) such that for every $k$ with $i \leq k \leq j$, house $k$ is not destroyed, then house $i$ and house $j$ are mutually reachable.

Li Yunlong is nervous after receiving the information. He wants to know, for each trapped soldier, how many houses he can reach.

Input Format

The first line contains two integers $n, m$.

Each of the next $m$ lines contains one of the three messages described above.

Output Format

For each trapped soldier, output the number of houses he can reach.

7 9
D 3
D 6
D 5
Q 4
Q 5
R
Q 4
R
Q 4

1
0
2
4

Hint

Constraints

$1 \leq n, m \leq 5 \times 10^4$.

If a soldier is trapped in a destroyed house, he can only wait to die.

Translated by ChatGPT 5