Dynamic array#5311
To implement a data structure that represents a dynamic array, you need to support the following operations:
Assign the value to the element at position .
Insert the number immediately after position (before position u+1, if it exists).
Determine how many numbers not exceeding are located between positions and , inclusive.
The elements in the array are indexed starting from one.
The first line contains two natural numbers and - the initial number of elements in the array and the number of operations, respectively (1 \leq n \leq 200000, 1 \leq m \leq 200000). The second line contains integers a_1, a_2, ..., a_n - the elements of the initial array (0 \leq a_i \leq 10^6). The following lines describe the operations in one of the following formats:
1 u p (u \geq 1, does not exceed the current size of the array, 0 \leq p \leq 10^6),
2 u p (u \geq 0, does not exceed the current size of the array, 0 \leq p \leq 10^6),
or
3 u v p (1 \leq u \leq v, does not exceed the current size of the array, 0 \leq p \leq 10^6).
The output should contain the results of the queries, each on a separate line.
Example 1