День рождения
День рождения
Крилик Стьюи подарил крилику Стэну на день рождения волшебный массив. Этот массив умеет делать две вещи: изменять любое число и отвечать на запрос вида "_сколько на отрезке от 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**" виведите в отдельной строке результат, который должен вычислить волшебный массив Стэна.
9 9 0 0 1 0 1 0 0 0 0 q 1 4 q 0 0 c 2 2 q 5 6 q 1 2 c 8 2 c 1 3 q 0 3 q 5 8
2 1 1 2 3 2