#include <bits/stdc++.h>
using namespace std;
vector<int> c,rez;
set<int> st;
int n=0,q=0,k=0,x=0,s=0,t=0,u=0;
struct segmentree{
vector<int> tree;
void init(){
tree.assign(200001,0);
}
void build(int x, int l, int r){
if(r-l==0){
tree[x]=c[l];
return;
}
int m=(l+r)/2;
build(x*2+1,l,m);
build(x*2+2,m+1,r);
tree[x]=tree[2*x+1]+tree[2*x+2];
}
void update(int x, int l, int r, int i, int v){
if(r-l==0){
tree[x]=v;
//cout<<'!'<<tree[x]<<'\n';
return;
}
int m=(l+r)/2;
if(i<=m) update(x*2+1,l,m,i,v);
else update(x*2+2,m+1,r,i,v);
tree[x]=tree[2*x+1]+tree[2*x+2];
}
int sum(int x, int lx, int rx, int l, int r){
if(lx>r||rx<l)return 0;
else if(lx>=l&&rx<=r){
//cout<<tree[x]<<' ';
return tree[x];
}
else{
int mx=(lx+rx)/2;
int lsum=sum(2*x+1,lx,mx,l,r);
int rsum=sum(2*x+2,mx+1,rx,l,r);
return lsum+rsum;
}
}
};
int main()
{
//ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
segmentree segtree;
cin>>n>>q>>k;
for(int i=0;i<n;i++){
cin>>x;
c.push_back(x);
st.insert(i);
}
segtree.init();
segtree.build(0,0,n);
for(int i=0;i<q;i++){
cin>>s>>t>>u;
if(s==1){//now t and u == a and b
t--;
c[t]=u;
if(u==0&&st.count(t)){
st.erase(t);
}else st.insert(t);
segtree.update(0,0,n,t,u);
}else if(s==2){
if(k>1){
auto lp=st.lower_bound(t-1);
while(lp!=st.end()&&*lp<u){
int pos=*lp;
c[pos]/=k;
segtree.update(0,0,n,pos,c[pos]);
auto it=next(lp,1);
if(c[pos]==0)st.erase(lp);
lp=it;
}
//segtree.build(0,0,n);
}
}else{
//cout<<'#';
rez.push_back(segtree.sum(0,0,n,t-1,u-1));
//cout<<'#' ;
}
//for(int y:c){cout<<y<<' ';}
//cout<<'\n';
}
for(int y:rez){
cout<<y<<'\n';
}
return 0;
}
