Динамічний масив

Потрібно реалізувати структуру даних, яка являє собою динамічний масив, який підтримує наступні операції:

1. Присвоїти числу, яке стоїть на позиції u, значення p.

2. Вставити число p після позиції u (але перед позицією u+1, якщо вона існує).

3. Повідомити, скільки чисел, які не перевищують p, стоїть на позиціях з u по v включно.

Елементи масиву нумеруються з одиниці.

Вхідні дані

У першому рядку знаходяться два натуральних числа n та m - початкова кількість елементів у масиві та кількість операцій (1 ≤ n ≤ 200000, 1 ≤ m ≤ 200000). У другому рядку знаходиться n цілих чисел a_1, a_2, ..., a_n - елементи початкового масиву (0 ≤ a_i ≤ 10^6). Наступні m рядків містять описи операцій у форматі

1 u p (u ≥ 1, u не перевищує поточного розміру масиву, 0 ≤ p ≤ 10^6),

2 u p (u ≥ 0, u не перевищує поточного розміру масиву, 0 ≤ p ≤ 10^6)

або

3 u v p (1 ≤ u ≤ v, v не перевищує поточного розміру масиву, 0 ≤ p ≤ 10^6).

Вихідні дані

У вихідному файлі повинні знаходитись відповіді на запити - по одній у рядку.

Приклади