题目描述

给定一个长度为 $n$ 的数组 $a$，以及 $q$ 个询问。另有一个无限长的二进制数组 $w$，初始时所有 $w_i=1$。

询问共有三种类型：

1. 1 x：翻转 $w_x$ 的值，即从 $1$ 变为 $0$，或从 $0$ 变为 $1$。
2. 2 l r：统计数组 $a$ 的区间 $[l,r]$ 中，有多少个不同的数满足 $w_{a_i}=1$ 且 $l \le i \le r$。
3. 3 x t：将 $a_x$ 赋值为 $t$。

请对每个第二类询问输出答案。

输入格式

第一行包含两个整数 $n,q$（$1 \le n,q \le 3 \cdot 10^5$），分别表示数组长度和询问数量。

第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$（$1 \le a_i \le 10^9$），表示数组初始值。

接下来 $q$ 行，每行首先包含一个整数 $type$（$1 \le type \le 3$），表示询问类型：

1. 若 $type=1$，则该询问还包含一个整数 $x$（$1 \le x \le 10^9$），表示翻转 $w_x$。
2. 若 $type=2$，则该询问还包含两个整数 $l,r$（$1 \le l \le r \le n$），表示询问区间 $[l,r]$ 中满足条件的不同数的数量。
3. 若 $type=3$，则该询问还包含两个整数 $x,t$（$1 \le x \le n$，$1 \le t \le 10^9$），表示把 $a_x$ 改为 $t$。

输出格式

对于每个第二类询问，单独输出一行答案。

输入 #1

10 5
3 4 3 4 3 2 3 1 2 1
2 2 5
1 3
2 2 5
3 4 5
2 2 5

输出 #1

2
1
2

评分方式

测试点分组如下：

1. $8$ 分：$n,q \le 10^3$；
2. $6$ 分：只有第二类询问，且 $n=q$，$l_i=1$，$r_i=i$；
3. $13$ 分：只有第二类询问；
4. $10$ 分：只有第一类和第二类询问，且所有 $a_i$ 两两不同；
5. $14$ 分：只有第一类和第二类询问，且所有 $w_{a_i}$ 至多改变一次；
6. $7$ 分：只有第一类和第二类询问；
7. $14$ 分：只有第二类和第三类询问；
8. $8$ 分：任意时刻都有 $a_i \le 100$；
9. $10$ 分：$n,q \le 5 \cdot 10^4$；
10. $10$ 分：无额外限制。