By Abner Samuel P. Palmeira, IFSULDEMINAS Brazil
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.
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.
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