День рождения
Крилик Стьюи подарил крилику Стэну на день рождения волшебный массив. Этот массив умеет делать две вещи: изменять любое число и отвечать на запрос вида "сколько на отрезке от a до b разных чисел".
Именно... Стэна больше волнует даже не подарок, а то, какую же гадость задумал Стьюи (мы же помним, что он не раз пытался убить Стэна). Стэн с опаской взял подарок и начал его рассматривать. На первый взгляд он выглядел совершенно безопасно. Стэн провёл пару простых операций и массив выдал вполне правильные операции.
Что-то тут не так, не мог Стьюи просто взять и подарить такой волшебный массив. Стэн просит помощи у вас, он собирается провести испытание - сделать ряд действий с массивом. Вам же нужно подготовить правильные ответы чтобы Стэн мог точно определить подделка ли этот волшебный массив или нет.
Входные данные
В первой строке содержится два целых числа n и m (1 ≤ n, m ≤ 50000). Вторая строка содержит n чисел - начальное содержимое массива. Последующие m строк содержат описание операций:
операция изменения в массиве имеет вид c x z, где x - целое число, позиция в массиве в которой нужно заменить текущее значение на число z (0 ≤ x < n);
операция запроса имеет вид q x y, где x, y (0 ≤ x ≤ y < n) - целые числа, соответственно начало и конец отрезка, на котором нужно посчитать количество различных чисел.
Все числа в массиве неотрицательные целые, по величине не превосходят 10^9.
Выходные данные
Для каждого запроса вида "q x y" виведите в отдельной строке результат, который должен вычислить волшебный массив Стэна.