Background

GTY is determined to alter human genes!!

Problem Description

GTY summoned $n$ people for experiments. GTY's house is very large, with $m$ rooms. At the beginning, everyone is in room $1$. GTY will either command someone to go wait in a certain room, or command a segment of rooms to start an experiment. An experiment yields some experimental information points, equal to the number of people in the room. If a specific group of people in a room has already done an experiment together, then that exact group will not add experimental information points again. This “no increase” applies to that group as a whole, not to each individual; that is, if $1,2,3$ have done an experiment together, then $1,2$ doing an experiment together again will still add $2$ points.

Input Format

The first line contains two integers $n,m,q (n,m,q \leq 10^5)$, denoting the number of people, the number of rooms, and the number of operations.

Then follow $q$ lines, each describing one operation: C i j means send person $i$ to room $j$; W l r means make all rooms in the interval $[l,r]$ conduct the experiment.

Output Format

For each W operation, output one number, the points obtained by that operation.

3 5 7
C 1 2
C 2 2
W 1 2
C 3 2
W 1 2
C 3 3
W 1 3

3
3
0

Hint

Make good use of STL.

Translated by ChatGPT 5