#include<bits/stdc++.h>
#define STIZE(x) fprintf(stderr, "STIZE%d\n", x);
#define PRINT(x) fprintf(stderr, "%s = %d\n", #x, x);
#define NL(x) printf("%c", " \n"[(x)]);
#define lld long long
#define pii pair<int,int>
#define pb push_back
#define fi first
#define se second
#define mid (l+r)/2
#define endl '\n'
#define all(a) begin(a),end(a)
#define sz(a) int((a).size())
#define LINF 1000000000000000LL
#define INF 1000000000
#define EPS 1e-9
using namespace std;
#define MAXN 100010
set<int> s;
vector<int> izbaciti;
lld bit[MAXN], a[MAXN];
lld query(int idx) {
lld rez = 0;
for( ; idx > 0; idx -= idx&-idx) rez += bit[idx];
return rez;
}
void update(int idx, lld val) {
val -= a[idx]; a[idx] += val;
for( ; idx < MAXN; idx += idx&-idx) bit[idx] += val;
}
int main() {
ios::sync_with_stdio(false);cin.tie(0);
lld N, Q, K, a1; cin >> N >> Q >> K;
for(int i = 1; i <= N; i++) {
cin >> a1; update(i, a1);
if(a[i] != 0) s.insert(i);
}
while(Q--) {
int type, u1, u2; cin >> type >> u1 >> u2;
if(type == 1) {
update(u1, u2);
if(u2 != 0) s.insert(u1);
else s.erase(u1);
} else if(type == 2) {
if(K == 1) continue;
for(auto it = s.lower_bound(u1); it != s.end() && *it <= u2; it++) {
update(*it, a[*it]/K);
if(a[*it] == 0) izbaciti.pb(*it);
}
for(auto x : izbaciti) s.erase(x);
izbaciti.clear();
} else {
cout << query(u2) - query(u1-1) << endl;
}
}
return 0;
}
