#include <bits/stdc++.h> #define ii pair<int, int> #define fi first #define se second #define inf 0x3f3f3f3f3f3f3f3f using namespace std; using ll = long long; const ll mod=1e9+7; const int nx=1e5+5; deque<ll> operator +(deque<ll> a, deque<ll> b) { deque<ll> c; int l=a.size(), r=b.size(); c.resize(max(l, r)); while(a.size()<c.size()) a.push_back(0); while(b.size()<c.size()) b.push_back(0); for(int i = 0; i < c.size(); i++) c[i]=a[i]+b[i]; return c; } int n, q, k, a[nx], la[nx<<2]; deque<ll> nod[nx<<2]; void build(int id, int l, int r) { la[id]=0; if(l==r) { nod[id].clear(); while(a[l]>0) nod[id].push_back(a[l]), a[l]/=k; return; } int mid=(l+r)>>1; build(id<<1, l, mid); build(id<<1|1, mid+1, r); nod[id]=nod[id<<1]+nod[id<<1|1]; } void down(int id) { if(!la[id]) return; for(int te = 1; te <= la[id]; te++) { for(int j = id*2; j <= id*2+1; j++) { la[j]++; if(nod[j].size()) nod[j].pop_front(); } } la[id]=0; } void upd(int id, int l, int r, int p, int val) { if(l>p || r<p) return; if(l==r) { nod[id].clear(); while(val>0) nod[id].push_back(val), val/=k; return; } int mid=(l+r)>>1; down(id); upd(id<<1, l, mid, p, val); upd(id<<1|1, mid+1, r, p, val); nod[id]=nod[id<<1]+nod[id<<1|1]; } void update(int id, int l, int r, int u, int v) { if(l>v || r<u) return; if(l>=u && r<=v) { if(nod[id].size()) nod[id].pop_front(); la[id]++; return; } int mid=(l+r)>>1; down(id); update(id<<1, l, mid, u, v); update(id<<1|1, mid+1, r, u, v); nod[id]=nod[id<<1]+nod[id<<1|1]; } ll get(int id, int l, int r, int u, int v) { if(l>v || r<u) return 0; if(l>=u && r<=v) return (nod[id].empty())?0:nod[id].front(); int mid=(l+r)>>1; down(id); return get(id<<1, l, mid, u, v)+get(id<<1|1, mid+1, r, u, v); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>q>>k; for(int i = 1; i <= n; i++) cin>>a[i]; build(1, 1, n); while(q--) { int e, x, y; cin>>e>>x>>y; if(e==1) upd(1, 1, n, x, y); else if(e==2) update(1, 1, n, x, y); else cout<<get(1, 1, n, x, y)<<'\n'; } }