SOLVE
LATER
Yet another interesting problem about queries!
You have an array of n integers and q queries on this array. There are two types of queries:
This problem will be very popular! So you should solve it before before it became mainstream.
Input format
The first line of input contains two space separated integers n and q (\(1 \leq n, q \leq 5 \cdot 10^5\)) - size of array and number of queries.
The second line of input contains n space separated integers \(a_i\) (\(1 \leq a_i \leq n\)) - the elements of the array before queries.
Then q lines follow. The i-th of them contains parameters of the i-th query.
The i-th line can be:
Output format
For each query of second type print number of occurrences of \(x_i\) on the segment \([a_i, b_i]\).
Initially array is \([3, 2, 1, 2]\).
First query: there are 2 occurrences of 2 on segment \([2, 4]\).
Second query changes array to \([3, 2, 2, 2]\).
Third query: there are 3 occurrences of 2 on segment \([2, 4]\).