#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
#define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
#define EACH(it,a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); ++it)
#define SZ(S) ((int) ((S).size()))
#define DEBUG(x) { cout << #x << " = " << x << endl; }
#define PR(a,n) { cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl; }
#define PR0(a,n) { cout << #a << " = "; REP(_,n) cout << a[_] << ' '; cout << endl; }
const int MN = 100111;
long long it[MN * 4];
long long power[MN];
int b, MOD, l, n;
long long add(long long a, long long b, long long len) {
return (a*power[len] + b) % MOD;
}
#define CT(X) ((X) << 1)
#define CP(X) (CT(X) + 1)
#define MID ((l + r) >> 1)
void update(int i, int l, int r, int u, long long val) {
if (u < l || r < u) return ;
if (l == r) { it[i] = val; return ; }
update(CT(i), l, MID, u, val);
update(CP(i), MID+1, r, u, val);
it[i] = add(it[CT(i)], it[CP(i)], r - MID);
}
vector< pair<long long, pair<int,int> > > all;
void visit(int i, int l, int r, int u, int v) {
if (v < l || r < u) return ;
if (u <= l && r <= v) {
all.push_back(make_pair(it[i], make_pair(l, r)));
return ;
}
visit(CT(i), l, MID, u, v);
visit(CP(i), MID+1, r, u, v);
}
long long get(int u, int v) {
all.clear();
visit(1, 1, l, u, v);
int len = 0;
long long res = 0;
FORD(i,all.size()-1,0) {
res = add(all[i].first, res, len);
len += all[i].second.second - all[i].second.first + 1;
}
return res;
}
int main() {
ios :: sync_with_stdio(false); cin.tie(NULL);
cout << (fixed) << setprecision(6);
while (cin >> b >> MOD >> l >> n && b) {
power[0] = 1;
FOR(i,1,l) power[i] = power[i-1] * b % MOD;
memset(it, 0, sizeof it);
while (n--) {
char typ; cin >> typ;
if (typ == 'E') {
int u, val; cin >> u >> val;
update(1, 1, l, u, val);
}
else {
int u, v; cin >> u >> v;
cout << get(u, v) << "\n";
}
}
cout << "-\n";
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgojZGVmaW5lIEZPUihpLGEsYikgZm9yKGludCBpPShhKSxfYj0oYik7IGk8PV9iOyBpKyspCiNkZWZpbmUgRk9SRChpLGEsYikgZm9yKGludCBpPShhKSxfYj0oYik7IGk+PV9iOyBpLS0pCiNkZWZpbmUgUkVQKGksYSkgZm9yKGludCBpPTAsX2E9KGEpOyBpPF9hOyBpKyspCiNkZWZpbmUgRUFDSChpdCxhKSBmb3IoX190eXBlb2YoYS5iZWdpbigpKSBpdCA9IGEuYmVnaW4oKTsgaXQgIT0gYS5lbmQoKTsgKytpdCkKI2RlZmluZSBTWihTKSAoKGludCkgKChTKS5zaXplKCkpKQoKI2RlZmluZSBERUJVRyh4KSB7IGNvdXQgPDwgI3ggPDwgIiA9ICIgPDwgeCA8PCBlbmRsOyB9CiNkZWZpbmUgUFIoYSxuKSB7IGNvdXQgPDwgI2EgPDwgIiA9ICI7IEZPUihfLDEsbikgY291dCA8PCBhW19dIDw8ICcgJzsgY291dCA8PCBlbmRsOyB9CiNkZWZpbmUgUFIwKGEsbikgeyBjb3V0IDw8ICNhIDw8ICIgPSAiOyBSRVAoXyxuKSBjb3V0IDw8IGFbX10gPDwgJyAnOyBjb3V0IDw8IGVuZGw7IH0KCmNvbnN0IGludCBNTiA9IDEwMDExMTsKbG9uZyBsb25nIGl0W01OICogNF07CmxvbmcgbG9uZyBwb3dlcltNTl07CgppbnQgYiwgTU9ELCBsLCBuOwoKbG9uZyBsb25nIGFkZChsb25nIGxvbmcgYSwgbG9uZyBsb25nIGIsIGxvbmcgbG9uZyBsZW4pIHsKICAgIHJldHVybiAoYSpwb3dlcltsZW5dICsgYikgJSBNT0Q7Cn0KCiNkZWZpbmUgQ1QoWCkgKChYKSA8PCAxKQojZGVmaW5lIENQKFgpIChDVChYKSArIDEpCiNkZWZpbmUgTUlEICgobCArIHIpID4+IDEpCnZvaWQgdXBkYXRlKGludCBpLCBpbnQgbCwgaW50IHIsIGludCB1LCBsb25nIGxvbmcgdmFsKSB7CiAgICBpZiAodSA8IGwgfHwgciA8IHUpIHJldHVybiA7CiAgICBpZiAobCA9PSByKSB7IGl0W2ldID0gdmFsOyByZXR1cm4gOyB9CiAgICB1cGRhdGUoQ1QoaSksIGwsIE1JRCwgdSwgdmFsKTsKICAgIHVwZGF0ZShDUChpKSwgTUlEKzEsIHIsIHUsIHZhbCk7CgogICAgaXRbaV0gPSBhZGQoaXRbQ1QoaSldLCBpdFtDUChpKV0sIHIgLSBNSUQpOwp9Cgp2ZWN0b3I8IHBhaXI8bG9uZyBsb25nLCBwYWlyPGludCxpbnQ+ID4gPiBhbGw7CnZvaWQgdmlzaXQoaW50IGksIGludCBsLCBpbnQgciwgaW50IHUsIGludCB2KSB7CiAgICBpZiAodiA8IGwgfHwgciA8IHUpIHJldHVybiA7CiAgICBpZiAodSA8PSBsICYmIHIgPD0gdikgewogICAgICAgIGFsbC5wdXNoX2JhY2sobWFrZV9wYWlyKGl0W2ldLCBtYWtlX3BhaXIobCwgcikpKTsKICAgICAgICByZXR1cm4gOwogICAgfQogICAgdmlzaXQoQ1QoaSksIGwsIE1JRCwgdSwgdik7CiAgICB2aXNpdChDUChpKSwgTUlEKzEsIHIsIHUsIHYpOwp9CmxvbmcgbG9uZyBnZXQoaW50IHUsIGludCB2KSB7CiAgICBhbGwuY2xlYXIoKTsKICAgIHZpc2l0KDEsIDEsIGwsIHUsIHYpOwogICAgaW50IGxlbiA9IDA7CiAgICBsb25nIGxvbmcgcmVzID0gMDsKICAgIEZPUkQoaSxhbGwuc2l6ZSgpLTEsMCkgewogICAgICAgIHJlcyA9IGFkZChhbGxbaV0uZmlyc3QsIHJlcywgbGVuKTsKICAgICAgICBsZW4gKz0gYWxsW2ldLnNlY29uZC5zZWNvbmQgLSBhbGxbaV0uc2Vjb25kLmZpcnN0ICsgMTsKICAgIH0KICAgIHJldHVybiByZXM7Cn0KCmludCBtYWluKCkgewogICAgaW9zIDo6IHN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7IGNpbi50aWUoTlVMTCk7CiAgICBjb3V0IDw8IChmaXhlZCkgPDwgc2V0cHJlY2lzaW9uKDYpOwogICAgd2hpbGUgKGNpbiA+PiBiID4+IE1PRCA+PiBsID4+IG4gJiYgYikgewogICAgICAgIHBvd2VyWzBdID0gMTsKICAgICAgICBGT1IoaSwxLGwpIHBvd2VyW2ldID0gcG93ZXJbaS0xXSAqIGIgJSBNT0Q7CgogICAgICAgIG1lbXNldChpdCwgMCwgc2l6ZW9mIGl0KTsKICAgICAgICB3aGlsZSAobi0tKSB7CiAgICAgICAgICAgIGNoYXIgdHlwOyBjaW4gPj4gdHlwOwogICAgICAgICAgICBpZiAodHlwID09ICdFJykgewogICAgICAgICAgICAgICAgaW50IHUsIHZhbDsgY2luID4+IHUgPj4gdmFsOwogICAgICAgICAgICAgICAgdXBkYXRlKDEsIDEsIGwsIHUsIHZhbCk7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgZWxzZSB7CiAgICAgICAgICAgICAgICBpbnQgdSwgdjsgY2luID4+IHUgPj4gdjsKICAgICAgICAgICAgICAgIGNvdXQgPDwgZ2V0KHUsIHYpIDw8ICJcbiI7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgY291dCA8PCAiLVxuIjsKICAgIH0KICAgIHJldHVybiAwOwp9Cgo=