#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; const int LG=30; int n, q, k, a[nx], la[nx<<2], st[nx<<2]; vector<ll> nod[nx<<2]; void mix(int id) { st[id]=0; int l=st[id<<1], r=st[id<<1|1]; int cur=0; for(int i = 0; i < LG; i++) { nod[id][cur++]=nod[id<<1][l]+nod[id<<1|1][r]; l=(l+1)%LG; r=(r+1)%LG; } } void build(int id, int l, int r) { nod[id].assign(LG, 0); st[id]=0; la[id]=0; if(l==r) { int cur=0; while(a[l]>0) nod[id][cur++]=a[l], a[l]/=k; return; } int mid=(l+r)>>1; build(id<<1, l, mid); build(id<<1|1, mid+1, r); mix(id); } 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]++; nod[j][st[j]]=0; st[j]=(st[j]+1)%LG; } } la[id]=0; } void upd(int id, int l, int r, int p, int val) { if(l>p || r<p) return; if(l==r) { st[id]=0; int cur=0; for(int i = 0; i < LG; i++) nod[id][i]=0; while(val>0) nod[id][cur++]=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); mix(id); } void update(int id, int l, int r, int u, int v) { if(l>v || r<u) return; if(l>=u && r<=v) { nod[id][st[id]]=0; st[id]=(st[id]+1)%LG; 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); mix(id); } 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][st[id]]; 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'; } }