День народження
Крілик Стью подарував крілику Стену на день народження чарівний масив. Цей масив уміє робити дві речі: заміняти будь-яке число і відповідати на запит вигляду "скільки на відрізку від 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" виведіть в окремому рядку результат, який повинен обчислити чарівний масив Стена.