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 109.

Output

Зкште the result of each query "**q x y**" in a separate line, so it's possible to compare it with the magic array.