Three Queries#384

Three Queries

4 saniyə
256 meqabayt
Very hard

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:

  1. "" — toggle the value of w_x (from to , and vice versa).

  2. "" — 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.

  3. "" — assign the value to a_x.

Provide an answer for each query of the second type.

Input

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:

  1. If type = 1, the query contains one integer (1 \le x \le 10^9) — toggle the value of w_x.

  2. 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.

  3. 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 .

Output

For each query of the second type, output the number of unique numbers in the range on a separate line.

Examples

Example 1

Loading
Loading

Note

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.

Scoring

  1. ( points): n, q \le 10^3;

  2. ( points): only queries of type ; n=q; l_i=1; r_i=i;

  3. ( points): only queries of type ;

  4. ( points): only queries of type and ; all a_i are pairwise distinct;

  5. ( points): only queries of type and ; all w_{a_i} can change only once;

  6. ( points): only queries of type and ;

  7. ( points): only queries of type and ;

  8. ( points): at any moment, a_i \le 100;

  9. ( points): n, q \le 5\cdot10^4;

  10. ( points): without additional constraints.