URI Online Judge | 2655

Dangerous Trail

By Abner Samuel P. Palmeira, IFSULDEMINAS BR Brazil

Timelimit: 1

Geraldo de Rívea is a witcher, and like every good witcher he prepares well, before facing a monster.

Geraldo wants to travel to Novigrad, for this he will have to cross a road that starts in the south and goes north straight, the big problem is that in every integer coordinate of that road there is a monster.

Since Geraldo does not like being caught unwarned he wants to know how many monster types exist from the X coordinates to the Y coordinate of that road.

To solve this problem Geraldo asked you to do a program that performs the following operations:

1 L R - Print how many different monsters there are from coordinate L to R on the road. 

2 C T - The monster of coordinate C is now a monster of type T.

Input

The first line contains three integers N, Q (1 ≤ N, Q ≤ 105) and M (1 ≤ M ≤ 50) representing the size of the road, the number of operations Geraldo wants to do, how many types of monsters Geraldo knows.

The second line will contain N integers x1, x2, ...., xn representing the type of monster that is initially in that position.

The next Q lines will contain Geraldo's queries, following the pattern described above.

Output

Print query responses.

Input Sample Output Sample

5 6 5

1 2 1 4 5

1 1 5

1 1 3

2 3 3

1 1 3

1 1 2

1 1 1

4

2

3

2

1