#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<ll,ll>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
const int nmax = 1e5 + 1;
vector <pll> t(4 * nmax);
vector <ll> T(4 * nmax);
vector <ll> a(nmax);
void build(int v, int l, int r){
if(l == r){
t[v] = {a[l], l};
T[v] = a[l];
return;
}
int m = (l + r) / 2;
build(2 * v, l, m);
build(2 * v+ 1, m + 1, r);
t[v] = max(t[v], t[2 * v]);
T[v] = T[2 * v] + T[2 * v + 1];
}
void update(int v, int l, int r, int pos, ll val){
if(l > pos || r < pos) return;
if(l == r){
t[v].f = T[v] = val;
return;
}
int m = (l + r) / 2;
update(2 * v, l, m, pos, val);
update(2 * v + 1, m + 1, r, pos, val);
t[v] = max(t[2 * v], t[2 * v + 1]);
T[v] = T[2 * v] + T[2 * v + 1];
}
pll get(int v, int l, int r, int st, int fin){
if(l > fin || r < st) return {0, 0};
if(l >= st && r <= fin)
return t[v];
int m = (l + r) /2;
pll x = get(2 * v, l, m, st, fin);
pll y = get(2 * v + 1, m + 1, r, st, fin);
return max(x, y);
}
ll get1(int v, int l, int r, int st, int fin){
if(l > fin || r < st) return 0;
if(l >= st && r <= fin)
return T[v];
int m = (l + r) /2;
ll x = get1(2 * v, l, m, st, fin);
ll y = get1(2 * v + 1, m + 1, r, st, fin);
return x + y;
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0);
int n, q, k; cin >> n >> q >> k;
for(int i = 1; i <= n; i++)
cin >> a[i];
build(1,1, n);
while(q--){
int t; cin >> t;
if(t == 1){
int pos, val; cin >> pos >> val;
update(1, 1, n, pos, val);
continue;
}
if(t == 2){
vector <pii> vec;
int l, r; cin >> l >> r;
if(k == 1) continue;
while(true){
pll u = get(1, 1, n, l, r);
if(!u.f) break;
u.f /= k;
update(1, 1, n, u.s, 0);
vec.pb(u);
}
for(auto to : vec)
update(1, 1, n, to.s, to.f);
continue;
}
if(t == 3){
int l, r; cin >> l >> r;
cout << get1(1, 1, n, l, r) << "\n";
}
}
return 0;
}
