Given an array of length and queries. We also have a binary array of infinite length, initially all w_i=1.
There are three types of queries:
"" — toggle the value of w_x (from to , and vice versa).
"" — count the number of unique numbers in the array in the range [l, r] for which w_{a_i}=1 and l \le i \le r.
"" — assign the value to a_x.
Provide an answer for each query of the second type.
The first line contains two integers and (1 \le n, q \le 3\cdot10^5) — the length of the array and the number of queries.
The second line contains integers a_1, a_2, \dots, a_n (1 \le a_i \le 10^9) — the values of the elements of the array.
Each of the following lines starts with an integer (1 \le type \le 3) — the type number of each query:
If type = 1, the query contains one integer (1 \le x \le 10^9) — toggle the value of w_x.
If type = 2, the query contains two integers and (1 \le l \le r \le n) — count the number of unique numbers in the array in the range [l, r] for which w_{a_i}=1 and l \le i \le r.
If type = 3, the query contains two integers and (1 \le x \le n, 1 \le t \le 10^9) — replace the value of a_x with .
For each query of the second type, output the number of unique numbers in the range on a separate line.
Example 1
In the example for the first query of the second type, the segment looks like [4, 3, 4, 3], meaning there are numbers , , and w_3, w_4 are equal to , so the answer is . After the next query of type , w_3 becomes , so for the next query, the answer is . After the next query, the array will look like [3, 4, 3, 5, 3, 2, 3, 1, 2, 1]. In the last query, the segment will look like [4, 3, 5, 3], meaning there are numbers , respectively the answer is , because w_3 = 0.
( points): n, q \le 10^3;
( points): only queries of type ; n=q; l_i=1; r_i=i;
( points): only queries of type ;
( points): only queries of type and ; all a_i are pairwise distinct;
( points): only queries of type and ; all w_{a_i} can change only once;
( points): only queries of type and ;
( points): only queries of type and ;
( points): at any moment, a_i \le 100;
( points): n, q \le 5\cdot10^4;
( points): without additional constraints.