Colorful Village

Interview

Time limit2sMemory limit512 MB

Summary

Maintain N houses under range repaint operations and answer queries counting how many of the T colors appear in a range.

Level: Medium6 of 10
Topics: Segment tree, Bit manipulation, Linked list, Array
Solved: No attempts yet

Problem

Minho manages the country of Cheon, which has N houses. To keep track of them he calls the houses 1, 2, ... N.

One day Minho decided he wanted to repaint every house in a chosen range with a single color, and also to ask how many different colors appear in a chosen range.

There are two kinds of operations.

C x y z: paint house x, house y, and every house between them with color z.
Q x y: print how many different colors appear on house x, house y, and every house between them.

Minho uses colors 1, 2, ... T, and at the start every house is painted with color 1.

Write a program that carries out Minho's operations in order.

Input

The first line contains N, T, and Q separated by spaces ( $1 \le N \le 100000$ , $1 \le T \le 30$ , $1 \le Q \le 100000$ ): the number of houses, the number of colors, and the number of operations.

Each of the next Q lines contains one operation, given as C x y z or Q x y, with $1 \le x \le N$ , $1 \le y \le N$ , and $1 \le z \le T$ . The value of x may be larger than y. In that case the operation still applies to the range between the two numbers, that is, houses $\min(x, y)$ through $\max(x, y)$ .

Output

For each Q x y operation, print on its own line how many different colors appear on house x, house y, and every house between them.

Examples2

Example 1
Input
```
2 2 4
C 1 1 2
Q 1 2
C 2 2 2
Q 1 2
```
Expected output
```
2
1
```
Example 2
Input
```
1 1 3
Q 1 1
C 1 1 1
Q 1 1
```
Expected output
```
1
1
```