#include <cstdio>
#include <map>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
map <int,int> mp;

int n, m, len;
int a[100002], b[100002];
short cnt[320][200002];//卡空间

inline int read(){
	int s=0,f=1;char c=getchar();
	while(c<'0' || c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0' && c<='9'){
		s=(s<<3)+(s<<1)+c-'0';
		c=getchar();
	}
	return s*f;
}

void Prepare(){
	for(int i = 1; i <= n; i += len){
		for(int j = i; j < i + len && j <= n; ++j){
			++cnt[i / len + 1][a[j]];
		}
	}
	return;
}

void Change(int x, int y){
	--cnt[(x - 1) / len + 1][a[x]];
	++cnt[(x - 1) / len + 1][y];
	a[x] = y;
	return;
}

int Work(int l, int r, int x){
	int lp = (l - 1) / len + 1;
	int rp = (r - 1) / len + 1;
	int ret = 0;
	if(lp == rp || lp == rp - 1){
		for(int i = l; i <= r; ++i){
			if(a[i] == x){
				++ret;
			}
		}
		return ret;
	}
	for(int i = l; i <= lp * len && i <= n; ++i){
		if(a[i] == x){
			++ret;
		}
	}
	for(int i = (rp - 1) * len + 1; i <= r; ++i){
		if(a[i] == x){
			++ret;
		}
	}
	for(int i = lp + 1; i <= rp - 1; ++i){
		ret += cnt[i][x];
	}
	return ret;
}

int main(){
// 	freopen("P2464.in","r",stdin);
// 	freopen("P2464.out","w",stdout);
	n = read(), m = read();
	for(int i = 1; i <= n; ++i){
		a[i] = b[i] = read();
	}
	len = (int)sqrt(n);
	sort(b + 1, b + n + 1);
	int nn = unique(b + 1, b + n + 1) - b - 1;
	for(int i = 1; i <= n; ++i){
		int tmp = a[i];
		a[i] = lower_bound(b + 1, b + nn + 1, a[i]) - b;
		mp[tmp] = a[i];
	}
	Prepare();
	while(m--){
		char c = getchar();
		while(c == ' ' || c == '\n' || c == '\r'){
			c = getchar();
		}
		if(c == 'C'){
			int x = read(), y = read();
			if(!mp.count(y)){
				mp[y] = ++nn;//可能加入未出现编号
			}
			Change(x, mp[y]);
		}
		if(c == 'Q'){
			int l = read(), r = read(), x = read();
			x = mp[x];
			printf("%d\n", Work(l, r, x));
		}
	}
	return 0;
}