题目描述

小J是国家图书馆的一位图书管理员，他的工作是管理一个巨大的书架。虽然他很能吃苦耐劳，但是由于这个书架十分巨大，所以他的工作效率总是很低，以致他面临着被解雇的危险，这也正是他所郁闷的。
具体说来，书架由N个书位组成，编号从1到N。每个书位放着一本书，每本书有一个特定的编码。
小J的工作有两类：
1.图书馆经常购置新书，而书架任意时刻都是满的，所以只得将某位置的书拿掉并换成新购的书。
2.小J需要回答顾客的查询，顾客会询问某一段连续的书位中某一特定编码的书有多少本。
例如，共5个书位，开始时书位上的书编码为1，2，3，4，5
一位顾客询问书位1到书位3中编码为“2”的书共多少本，得到的回答为：1
一位顾客询问书位1到书位3中编码为“1”的书共多少本，得到的回答为：1
此时，图书馆购进一本编码为“1”的书，并将它放到2号书位。
一位顾客询问书位1到书位3中编码为“2”的书共多少本，得到的回答为：0
一位顾客询问书位1到书位3中编码为“1”的书共多少本，得到的回答为：2
……
你的任务是写一个程序来回答每个顾客的询问。

输入格式：

第一行两个整数N，M，表示一共N个书位，M个操作。
接下来一行共N个整数数A1,A2…AN，Ai表示开始时位置i上的书的编码。
接下来M行，每行表示一次操作，每行开头一个字符
若字符为‘C’，表示图书馆购进新书，后接两个整数A(1<=A<=N)，P，表示这本书被放在位置A上，以及这本书的编码为P。
若字符为‘Q’，表示一个顾客的查询，后接三个整数A，B，K(1<=A<=B<=N)，表示查询从第A书位到第Ｂ书位（包含Ａ和Ｂ）中编码为Ｋ的书共多少本。

输出格式：

对每一个顾客的查询，输出一个整数，表示顾客所要查询的结果。

输入样例#1：

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
1
0
2

说明/提示

对于40% 的数据，1≤N,M≤5000。

对于100% 的数据，1≤N,M≤10^5。

对于100% 的数据，所有出现的书的编码为不大于 2^31 - 1的正数。