Candy Country Cloud Catch

In the magical Candy Country, the sky is filled with uniquely colored candy clouds. Each cloud, represented as a segment (or a point if the segment degenerates), moves horizontally between the boundaries 0 (left) and len (right) in the sky. Every unit time, each cloud moves one unit in its current direction. When a cloud moving left has its left endpoint reach 0, it reverses to move right; when a cloud moving right has its right endpoint reach len, it reverses to move left.

At various moments, new clouds will appear or existing clouds will vanish. Moreover, at any moment, each cloud continuously drops candies of its unique color straight down (assume the falling time is negligible). At time T, you (as little Z) take out a pocket that covers the horizontal interval [L, R]. If there exists any position x in [L, R] where a candy drops (i.e. x is covered by some cloud’s current horizontal span), then you catch the candy of that cloud’s color.

Your task is to process a sequence of events and answer the queries: at a given query time, how many distinct candy colors (i.e. clouds) will drop candies into the pocket? The events are of three types:

• Appearance event: A cloud appears at time T. It is described by: A T id L R D, where id is a unique identifier, the cloud initially spans the interval [L, R] (0 ≤ L ≤ R ≤ len) and has initial direction D (1 for right, -1 for left).
• Removal event: A cloud disappears at time T. It is described by: R T id. Note that if a cloud is removed at time T, it is not considered for any query at time T or later.
• Query event: At time T, you use a pocket covering the interval [L, R] to catch candies. It is described by: Q T L R. You must determine how many clouds (i.e. candy colors) currently have at least one point of their horizontal span intersecting [L, R].

Movement details: For a cloud that appears at time T₀ with initial left endpoint L₀ and segment length seg = R - L, define M = len - seg. The cloud’s left endpoint moves like a point bouncing between 0 and M. Formally, if the cloud’s initial direction is d (either 1 or -1), then at time T (T ≥ T₀), let Δ = T - T₀. If M = 0 then the cloud stays fixed at 0; otherwise, compute:

\[ \text{pos} = L_0 + d \times \Delta \]

Then let the period be \(P=2\times M\). Define

\[ r = ((\text{pos} \mod P) + P) \mod P. \]

Finally, the effective left endpoint at time T is:

\[ x = \begin{cases} r, & r \le M \\ 2M - r, & r > M \end{cases} \]

The cloud then covers the interval [x, x+seg]. For each query event, count every active cloud (i.e. those that have appeared but not yet been removed) whose current interval [x, x+seg] intersects the query interval [L, R] (an intersection exists if \(\max(x, L) \le \min(x+seg, R)\)).

Input format:

• The first line contains two integers: len and Q — the right boundary of the sky and the number of events.
• The following Q lines each contain an event in one of the following formats:
  • A T id L R D — a cloud appears at time T with id, covering [L, R] and moving in direction D (1 for right, -1 for left).
  • R T id — the cloud with id is removed at time T.
  • Q T L R — a query at time T asking for the number of clouds that currently drop candies into a pocket covering [L, R].

Output format:

• For each query event (in the order they appear in the input), output one integer on a new line — the number of distinct candy colors (clouds) caught by the pocket at that time.

inputFormat

The first line contains two integers len and Q.

Each of the next Q lines contains an event in one of the three formats described above.

len Q
A T id L R D
R T id
Q T L R

outputFormat

For each query event in the input, output a single integer on a new line representing the number of clouds whose current candy drop (cloud segment) intersects with the pocket interval.

sample

10 6
A 1 1 2 4 1
A 2 2 0 2 -1
Q 3 3 5
R 4 1
Q 5 0 3
Q 6 5 10

2
1
1

</p>