#include <bits/stdc++.h> using namespace std; #define int long long #define pb push_back #define emb emplace_back #define fr first #define sc second #define all(x) x.begin(),x.end() #define sp << " " << #define N 100000 #define inf 1e9 typedef pair<int,int> ii; typedef tuple<int,int,int> iii; typedef array<int,30> arr30; arr30 operator+(arr30 a,arr30 b){ arr30 ans{}; for(int i=0;i<30;i++) ans[i]=a[i]+b[i]; return ans; } arr30 ff(int x,int k){ arr30 ans{}; for(int i=0;x;i++,x/=k) ans[i]=x%k; return ans; } arr30 st[4*N]; int lz[4*N]; void push(int x){ if(lz[x]==0) return; if(x<2*N){ lz[x<<1]+=lz[x]; lz[x<<1|1]+=lz[x]; } for(int i=0;i<30;i++){ if(i+lz[x]<30) st[x][i]=st[x][i+lz[x]]; else st[x][i]=0; } lz[x]=0; } void update(int x,int l,int r,int qx,arr30 val){ push(x); if(r<qx || qx<l) return; if(l==r){ st[x]=val; return; } int mid=(l+r)/2; update(x<<1,l,mid,qx,val); update(x<<1|1,mid+1,r,qx,val); st[x]=st[x<<1]+st[x<<1|1]; } void update(int x,int l,int r,int ql,int qr){ push(x); if(r<ql || qr<l) return; if(ql<=l && r<=qr){ lz[x]++; push(x); return; } int mid=(l+r)/2; update(x<<1,l,mid,ql,qr); update(x<<1|1,mid+1,r,ql,qr); st[x]=st[x<<1]+st[x<<1|1]; } arr30 query(int x,int l,int r,int ql,int qr){ if(r<ql || qr<l) return arr30{}; push(x); if(ql<=l && r<=qr) return st[x]; int mid=(l+r)/2; return query(x<<1,l,mid,ql,qr)+query(x<<1|1,mid+1,r,ql,qr); } void solve(){ int n,q,k; cin >> n >> q >> k; for(int i=1;i<=n;i++){ int x;cin >> x; update(1,1,n,i,ff(x,k)); } while(q--){ int s,t,u; cin >> s >> t >> u; if(s==1) update(1,1,n,t,ff(u,k)); if(s==2) update(1,1,n,t,u); if(s==3){ arr30 a=query(1,1,n,t,u); int ans=0; for(int i=0,j=1;i<30 && j<=1e9;i++,j*=k) ans+=a[i]*j; cout << ans << "\n"; } } } int32_t main(){ cout << fixed << setprecision(0); ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); int test=1; //~ cin >> test; while(test--){ solve(); } }