#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
llo n,q,k;
llo aa,bb,cc;
llo it[100001];
llo tree[100001];
void u(llo i,llo j){
while(i<=100000){
tree[i]+=j;
i+=(i&-i);
}
}
llo s(llo i){
llo su=0;
while(i>0){
su+=tree[i];
i-=(i&-i);
}
return su;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n>>q>>k;
set<pair<llo,llo>> ss;
for(llo i=0;i<n;i++){
cin>>it[i];
u(i+1,it[i]);
ss.insert({i,it[i]});
}
for(llo i=0;i<q;i++){
cin>>aa>>bb>>cc;
if(aa==1){
if(it[bb-1]>0){
ss.erase({bb-1,it[bb-1]});
}
u(bb,-it[bb-1]);
it[bb-1]=cc;
u(bb,cc);
if(cc>0){
ss.insert({bb-1,it[bb-1]});
}
}
else if(aa==2){
if(k>1){
auto j=ss.lower_bound({bb-1,0});
while((*j).a<cc and j!=ss.end()){
llo ind=(*j).a;
u(ind+1,-it[ind]);
pair<llo,llo> kk=*j;
ss.erase(j);
it[ind]=it[ind]/k;
if(it[ind]>0){
u(ind+1,it[ind]);
ss.insert({ind,it[ind]});
}
j=ss.upper_bound(kk);
}
}
}
else{
cout<<s(cc)-s(bb-1)<<endl;
}
}
return 0;
}
