题目描述

给你一个长度为 $n$ 的数列 $a_1, a_2, \ldots, a_n$。

接下来会有 $m$ 次操作，操作分为如下两种类型：

• C p x：将 $a_p$ 的值更新为 $x$；
• Q l r x：查询下标区间 $[l, r]$ 范围内有多少个数等于 $x$。

依次执行 $m$ 次操作，并且对于每次查询操作，输出对应的结果。

输入格式

第一行，两个整数 $n$ 和 $m$，以一个空格分隔（$1 \le n, m \le 10^5$）。

第二行，$n$ 个整数 $a_1, a_2, \ldots, a_n$，两两之间以一个空格分隔（$1 \le a_i \le 10^9$）。

接下来 $m$ 行，每行包含一个操作。

• 对于 C p x 操作，保证 $1 \le p \le n, 1 \le x \le 10^9$
• 对于 Q l r x 操作，保证 $1 \le l \le r \le n, 1 \le x \le 10^9$

输出格式

对于每次查询操作，输出一行，包含一个整数，表示答案。

样例

5 5
1 2 3 4 5
Q 1 3 2
Q 1 3 1
C 2 1
Q 1 3 2
Q 1 3 1

1
1
0
2

说明/提示

数据规模与约定

• 对于 $40\%$ 的数据，$n,m \le 5000; a_i, x \le 10^5$
• 对于 $100\%$ 的数据，$n,m \le 10^5; a_i, x \le 10^9$