Birthday
Rabbit Stewie presented a magic array for Stan on his birthday. This array is able to do two things: replace any number and answer the query of form "how many different numbers at the interval from a to b?"
Stan liked the gift, but he was concerned if this present was not a usual joke from Stewie. At first glance, everything was fair: Stan completed a few simple operations, and the array produced fully correct answers. To overcome all sorts of doubts, Stan asks for your help: he's going to thoroughly test the presented array, by a set of operations. You have to prepare the correct answers, so Stan could accurately determine whether an array of truly magical.
Input
The first line contains two integers n and m (1 ≤ n, m ≤ 50000). The second like contains n numbers - the initial array. The following m lines contain the description of the operations:
Replacement is determined by: c x z, where integer x is the index of array element which value should be changed to z (0 ≤ x < n);
Query is determined by q x y, where integers x, y – are beginning and the end of interval where the amount of different numbers should be calculated (0 ≤ x ≤ y < n) .
All numbers in arrays are not negative and do not exceed 10^9.
Output
Зкште the result of each query "q x y" in a separate line, so it's possible to compare it with the magic array.