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