Description

The color board has length $L$, where $L$ is a positive integer, so we can evenly divide it into $L$ small squares, each $1$ centimeter long, labeled from left to right as $1, 2, \dots, L$.

Currently the board has only one color. The teacher tells Abao that only two operations are allowed on the board:

1. C A B C means to paint all squares numbered from $A$ to $B$ with color $C$.
2. P A B means a query: how many different colors appear among squares numbered from $A$ to $B$.

There are $T$ types of paint in the school’s paint box. For simplicity, we label them as $1, 2, \dots, T$. Initially, the entire board has color $1$. Facing such a complex problem, Abao asks for your help. Can you help him?

Input Format

The first line contains $3$ integers $L$ $(1 \le L \le 10^5)$, $T$ $(1 \le T \le 30)$, and $O$ $(1 \le O \le 10^5)$. Here $O$ is the number of operations.

Then follow $O$ lines, each describing an operation in the form C A B C or P A B (here $A, B, C$ are integers; it is possible that $A > B$, in which case you should swap $A$ and $B$).

Output Format

For each query from the teacher, output the corresponding answer. Print one integer per line.

2 2 4
C 1 1 2
P 1 2
C 2 2 2
P 1 2

2
1

Hint

Constraints

$1 \le L \le 10^5$, $1 \le T \le 30$, $1 \le O \le 10^5$.

$1 \le A, B \le L$ (not guaranteed that $A \le B$), $1 \le C \le T$.

Translated by ChatGPT 5