Крилик Стьюи подарил крилику Стэну на день рождения волшебный массив. Этот массив умеет делать две вещи: изменять любое число и отвечать на запрос вида "_сколько на отрезке от 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) - целые числа, соответственно начало и конец отрезка, на котором нужно посчитать количество различных чисел.

Все числа в массиве неотрицательные целые, по величине не превосходят 109.

Выходные данные

Для каждого запроса вида "**q x y**" виведите в отдельной строке результат, который должен вычислить волшебный массив Стэна.