Turntable Channels

Time limit: 3000 msMemory limit: 256 MB

A studio has $N$ reversible turntables in a row and $K$ sound channels numbered $1,2,\ldots,K$ .

Turntable $i$ has a current permutation $P_i$ of the channels and a manual price $C_i$ . When a signal enters turntable $i$ on channel $x$ , exactly one of the following happens:

The signal follows the turntable for free and leaves on channel $P_i(x)$ .
The engineer pays $C_i$ and chooses any output channel $y$ with .

A request through interval $[L,R]$ sends the signal through turntables $L,L+1,\ldots,R$ in that order. The total payment is the sum of prices paid at turntables where the engineer manually chooses the output.

You must process $Q$ operations of three kinds:

Invert every turntable in an interval. For each affected turntable $i$ , its current permutation $P_i$ is replaced by the inverse permutation $P_i^{-1}$ , while does not change.

Input

The first line contains three integers $N$ , $K$ , and $Q$ ( $1 \le N,Q \le 2 \cdot 10^5$ , ), the number of turntables, the number of channels, and the number of operations.

Output

For each operation whose first token is A, print one line containing the minimum possible total payment for that request. Print the answers in the same order as the corresponding operations appear in the input. If there are no operations whose first token is A, print nothing.

Samples

Sample 1

Input

2 3 5
5 2 3 1
4 3 1 2
A 1 2 1 1
I 2 2
A 1 2 1 1
S 1 2 1 3 2
A 1 2 2 2

Output

0
4
2

The first request can follow channel $1 \to 2 \to 1$ for total payment $0$ . After inverting the second turntable, paying $4$ at the second turntable can finish on channel $1$ . After the replacement, paying $2$ at the first turntable can make the final channel equal to .

Turntable Channels

Input

Output

Samples

Sample 1

Submit

Submissions