#include<bits/stdc++.h>
#define int long long
using namespace std;
int ar[100005];
int n,q,k;
struct segtree{
deque<int>info[400005];
int sum[400005];
int lz[400005];
void push(int st,int en,int i){
if(lz[i]==0)return;
if(st!=en)lz[i*2]+=lz[i],lz[i*2+1]+=lz[i];
while(lz[i]>0&&info[i].size()>0){
sum[i]-=info[i].front();
info[i].pop_front();
lz[i]--;
}
lz[i]=0;
}
deque<int> merge(deque<int>l,deque<int>r){
int n=max(l.size(),r.size());
deque<int>a;
if(n==0)return a;
a.resize(n);
for(int i=0;i<n;i++){
if(i<l.size())a[i]+=l[i];
if(i<r.size())a[i]+=r[i];
}
return a;
}
void upd(int st,int en,int i,int pos,int val){
push(st,en,i);
if(st>pos||en<pos)return;
if(st==en){
info[i].clear();
int prv=val;
while(1){
int cur=prv/k;
if(cur==prv)break;
info[i].push_back(prv-cur);
prv=cur;
}
sum[i]=val;
return;
}
int m=(st+en)/2;
upd(st,m,i*2,pos,val);
upd(m+1,en,i*2+1,pos,val);
info[i]=merge(info[i*2],info[i*2+1]);
sum[i]=sum[i*2]+sum[i*2+1];
}
void water(int st,int en,int i,int l,int r){
push(st,en,i);
if(st>r||en<l)return;
if(st>=l&&en<=r){
lz[i]=1;
push(st,en,i);
return;
}
int m=(st+en)/2;
water(st,m,i*2,l,r);
water(m+1,en,i*2+1,l,r);
info[i]=merge(info[i*2],info[i*2+1]);
sum[i]=sum[i*2]+sum[i*2+1];
}
int fans(int st,int en,int i,int l,int r){
push(st,en,i);
if(st>r||en<l)return 0;
if(st>=l&&en<=r)return sum[i];
int m=(st+en)/2;
return fans(st,m,i*2,l,r)+fans(m+1,en,i*2+1,l,r);
}
}tr;
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>n>>q>>k;
for(int i=1;i<=n;i++)cin>>ar[i];
for(int i=1;i<=n;i++)tr.upd(1,n,1,i,ar[i]);
//cerr<<"work\n";
for(int i=0;i<q;i++){
int s,t,u;cin>>s>>t>>u;
//cerr<<s<<" "<<t<<' '<<u<<"\n";
if(s==1){
tr.upd(1,n,1,t,u);
}else if(s==2){
tr.water(1,n,1,t,u);
}else{
cout<<tr.fans(1,n,1,t,u)<<"\n";
}
}
}
