#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
const int mxN = 1e5 + 5;
vector<int> primes;
int lazy[mxN * 4], a[mxN], n;
bool vis[mxN];
struct node {
int val;
int cnt;
} tree[mxN * 4];
bool is_prime(int x) {
if(x == 1)
return false;
for(int p : primes)
if(x % p == 0 && x != p)
return false;
return true;
}
void propagate(int x, int lx, int rx) {
if(lazy[x] == -1)
return;
tree[x].val = lazy[x];
tree[x].cnt = 0;
if(lazy[x] <= 1e7 && is_prime(lazy[x]))
tree[x].cnt = rx - lx;
if(rx - lx == 1) {
lazy[x] = -1;
return;
}
lazy[2 * x + 1] = lazy[2 * x + 2] = lazy[x];
lazy[x] = -1;
}
void build(int x = 0, int lx = 0, int rx = n) {
if(rx - lx == 1) {
tree[x].val = a[lx];
if(a[lx] <= 1e7)
tree[x].cnt = is_prime(a[lx]);
return;
}
int mid = (lx + rx) / 2;
build(2 * x + 1, lx, mid);
build(2 * x + 2, mid, rx);
tree[x].cnt = tree[2 * x + 1].cnt + tree[2 * x + 2].cnt;
}
void update_point(int node, int v, int x = 0, int lx = 0, int rx = n) {
propagate(x, lx, rx);
if(rx - lx == 1) {
tree[x].val += v;
tree[x].cnt = 0;
if(tree[x].val <= 1e7 && is_prime(tree[x].val))
tree[x].cnt = 1;
return;
}
int mid = (lx + rx) / 2;
if(node < mid)
update_point(node, v, 2 * x + 1, lx, mid);
else
update_point(node, v, 2 * x + 2, mid, rx);
tree[x].cnt = tree[2 * x + 1].cnt + tree[2 * x + 2].cnt;
}
void range_update(int l, int r, int v, int x = 0, int lx = 0, int rx = n) {
propagate(x, lx, rx);
if(lx >= l && rx <= r) {
lazy[x] = v;
propagate(x, lx, rx);
return;
}
if(lx >= r || l >= rx)
return;
int mid = (lx + rx) / 2;
range_update(l, r, v, 2 * x +1, lx, mid);
range_update(l, r, v, 2 * x +2, mid, rx);
tree[x].cnt = tree[2 * x + 1].cnt + tree[2 * x + 2].cnt;
}
int query(int l, int r, int x = 0, int lx = 0, int rx = n) {
propagate(x, lx, rx);
if(lx >= l && rx <= r)
return tree[x].cnt;
if(lx >= r || l >= rx)
return 0;
int mid = (lx + rx) / 2;
int c1 = query(l, r, 2 * x + 1, lx, mid);
int c2 = query(l, r, 2 * x +2, mid, rx);
return c1 + c2;
}
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int q;
cin >> n >> q;
for(int i = 0; i < n; ++i)
cin >> a[i];
memset(lazy, -1, sizeof lazy);
for(int i = 2; i <= 1e3; ++i) {
if(vis[i])
continue;
primes.push_back(i);
for(int j = i + i; j <= 1e3; j += i)
vis[j] = true;
}
build();
while(q--) {
char c;
cin >> c;
if(c == 'A') {
int v, pos;
cin >> v >> pos;
--pos;
update_point(pos, v);
}
else if(c == 'R') {
int v, l, r;
cin >> v >> l >> r;
--l;
range_update(l, r, v);
}
else {
int l, r;
cin >> l >> r;
--l;
cout << query(l, r) << '\n';
}
}
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8Y3N0cmluZz4KI2luY2x1ZGUgPHZlY3Rvcj4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmNvbnN0IGludCBteE4gPSAxZTUgKyA1Owp2ZWN0b3I8aW50PiBwcmltZXM7CmludCBsYXp5W214TiAqIDRdLCBhW214Tl0sIG47CmJvb2wgdmlzW214Tl07CgpzdHJ1Y3Qgbm9kZSB7CglpbnQgdmFsOwoJaW50IGNudDsKfSB0cmVlW214TiAqIDRdOwoKYm9vbCBpc19wcmltZShpbnQgeCkgewoJaWYoeCA9PSAxKQoJCXJldHVybiBmYWxzZTsKCWZvcihpbnQgcCA6IHByaW1lcykKCQlpZih4ICUgcCA9PSAwICYmIHggIT0gcCkKCQkJcmV0dXJuIGZhbHNlOwoJcmV0dXJuIHRydWU7Cn0KCnZvaWQgcHJvcGFnYXRlKGludCB4LCBpbnQgbHgsIGludCByeCkgewoJaWYobGF6eVt4XSA9PSAtMSkKCQlyZXR1cm47Cgl0cmVlW3hdLnZhbCA9IGxhenlbeF07Cgl0cmVlW3hdLmNudCA9IDA7CglpZihsYXp5W3hdIDw9IDFlNyAmJiBpc19wcmltZShsYXp5W3hdKSkKCQl0cmVlW3hdLmNudCA9IHJ4IC0gbHg7CglpZihyeCAtIGx4ID09IDEpIHsKCQlsYXp5W3hdID0gLTE7CgkJcmV0dXJuOwoJfQoJbGF6eVsyICogeCArIDFdID0gbGF6eVsyICogeCArIDJdID0gbGF6eVt4XTsKCWxhenlbeF0gPSAtMTsKfQoKdm9pZCBidWlsZChpbnQgeCA9IDAsIGludCBseCA9IDAsIGludCByeCA9IG4pIHsKCWlmKHJ4IC0gbHggPT0gMSkgewoJCXRyZWVbeF0udmFsID0gYVtseF07CgkJaWYoYVtseF0gPD0gMWU3KQoJCQl0cmVlW3hdLmNudCA9IGlzX3ByaW1lKGFbbHhdKTsKCQlyZXR1cm47Cgl9CglpbnQgbWlkID0gKGx4ICsgcngpIC8gMjsKCWJ1aWxkKDIgKiB4ICsgMSwgbHgsIG1pZCk7CglidWlsZCgyICogeCArIDIsIG1pZCwgcngpOwoJdHJlZVt4XS5jbnQgPSB0cmVlWzIgKiB4ICsgMV0uY250ICsgdHJlZVsyICogeCArIDJdLmNudDsKfQoKdm9pZCB1cGRhdGVfcG9pbnQoaW50IG5vZGUsIGludCB2LCBpbnQgeCA9IDAsIGludCBseCA9IDAsIGludCByeCA9IG4pIHsKCXByb3BhZ2F0ZSh4LCBseCwgcngpOwoJaWYocnggLSBseCA9PSAxKSB7CgkJdHJlZVt4XS52YWwgKz0gdjsKCQl0cmVlW3hdLmNudCA9IDA7CgkJaWYodHJlZVt4XS52YWwgPD0gMWU3ICYmIGlzX3ByaW1lKHRyZWVbeF0udmFsKSkKCQkJdHJlZVt4XS5jbnQgPSAxOwoJCXJldHVybjsKCX0KCWludCBtaWQgPSAobHggKyByeCkgLyAyOwoJaWYobm9kZSA8IG1pZCkKCQl1cGRhdGVfcG9pbnQobm9kZSwgdiwgMiAqIHggKyAxLCBseCwgbWlkKTsKCWVsc2UKCQl1cGRhdGVfcG9pbnQobm9kZSwgdiwgMiAqIHggKyAyLCBtaWQsIHJ4KTsKCXRyZWVbeF0uY250ID0gdHJlZVsyICogeCArIDFdLmNudCArIHRyZWVbMiAqIHggKyAyXS5jbnQ7Cn0KCnZvaWQgcmFuZ2VfdXBkYXRlKGludCBsLCBpbnQgciwgaW50IHYsIGludCB4ID0gMCwgaW50IGx4ID0gMCwgaW50IHJ4ID0gbikgewoJcHJvcGFnYXRlKHgsIGx4LCByeCk7CglpZihseCA+PSBsICYmIHJ4IDw9IHIpIHsKCQlsYXp5W3hdID0gdjsKCQlwcm9wYWdhdGUoeCwgbHgsIHJ4KTsKCQlyZXR1cm47Cgl9CglpZihseCA+PSByIHx8IGwgPj0gcngpCgkJcmV0dXJuOwoJaW50IG1pZCA9IChseCArIHJ4KSAvIDI7CglyYW5nZV91cGRhdGUobCwgciwgdiwgMiAqIHggKzEsIGx4LCBtaWQpOwoJcmFuZ2VfdXBkYXRlKGwsIHIsIHYsIDIgKiB4ICsyLCBtaWQsIHJ4KTsKCXRyZWVbeF0uY250ID0gdHJlZVsyICogeCArIDFdLmNudCArIHRyZWVbMiAqIHggKyAyXS5jbnQ7Cn0KCmludCBxdWVyeShpbnQgbCwgaW50IHIsIGludCB4ID0gMCwgaW50IGx4ID0gMCwgaW50IHJ4ID0gbikgewoJcHJvcGFnYXRlKHgsIGx4LCByeCk7CglpZihseCA+PSBsICYmIHJ4IDw9IHIpCgkJcmV0dXJuIHRyZWVbeF0uY250OwoJaWYobHggPj0gciB8fCBsID49IHJ4KQoJCXJldHVybiAwOwoJaW50IG1pZCA9IChseCArIHJ4KSAvIDI7CglpbnQgYzEgPSBxdWVyeShsLCByLCAyICogeCArIDEsIGx4LCBtaWQpOwoJaW50IGMyID0gcXVlcnkobCwgciwgMiAqIHggKzIsIG1pZCwgcngpOwoJcmV0dXJuIGMxICsgYzI7Cn0KIAppbnQgbWFpbigpIHsKCWlvczo6c3luY193aXRoX3N0ZGlvKGZhbHNlKSwgY2luLnRpZShudWxscHRyKSwgY291dC50aWUobnVsbHB0cik7CglpbnQgcTsKCWNpbiA+PiBuID4+IHE7Cglmb3IoaW50IGkgPSAwOyBpIDwgbjsgKytpKQoJCWNpbiA+PiBhW2ldOwoJbWVtc2V0KGxhenksIC0xLCBzaXplb2YgbGF6eSk7Cglmb3IoaW50IGkgPSAyOyBpIDw9IDFlMzsgKytpKSB7CgkJaWYodmlzW2ldKQoJCQljb250aW51ZTsKCQlwcmltZXMucHVzaF9iYWNrKGkpOwoJCWZvcihpbnQgaiA9IGkgKyBpOyBqIDw9IDFlMzsgaiArPSBpKQoJCQl2aXNbal0gPSB0cnVlOwoJfQoJYnVpbGQoKTsKCXdoaWxlKHEtLSkgewoJCWNoYXIgYzsKCQljaW4gPj4gYzsKCQlpZihjID09ICdBJykgewoJCQlpbnQgdiwgcG9zOwoJCQljaW4gPj4gdiA+PiBwb3M7CgkJCS0tcG9zOwoJCQl1cGRhdGVfcG9pbnQocG9zLCB2KTsKCQl9CgkJZWxzZSBpZihjID09ICdSJykgewoJCQlpbnQgdiwgbCwgcjsKCQkJY2luID4+IHYgPj4gbCA+PiByOwoJCQktLWw7CgkJCXJhbmdlX3VwZGF0ZShsLCByLCB2KTsKCQl9CgkJZWxzZSB7CgkJCWludCBsLCByOwoJCQljaW4gPj4gbCA+PiByOwoJCQktLWw7CgkJCWNvdXQgPDwgcXVlcnkobCwgcikgPDwgJ1xuJzsKCQl9Cgl9Cn0K