#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define pb push_back
using ll = long long ;
//#define int long long
using ii = pair < int , int > ;
const int MAX = 1e5+4,mod=1e9+7;
const int inf=0x3f3f3f3f;
int K;
vector < ii > pr[MAX];
void minn(int &a , int b){
if(b<a) a=b;
}
void maxx(int &a , int b){
if(b>a) a=b;
}
int LZ[MAX*4];
int ST[30][MAX*4];
int val;
int a[MAX];
void up (int x,int id,int l,int r){
if(l==r){
int z=0;
while(val!=0){
ST[z++][id]=val%K;
val/=K;
}
for(z;z<30;z++) ST[z][id]=0;
return;
}
int mid=l+r>>1;
if(LZ[id]){
minn(LZ[id],30);
LZ[id<<1]+=LZ[id];
LZ[id<<1|1]+=LZ[id];
for(int i=0;i<30-LZ[id];i++) ST[i][id<<1]=ST[i+LZ[id]][id<<1],ST[i][id<<1|1]=ST[i+LZ[id]][id<<1|1];;
for(int i=30-LZ[id];i<30;i++) ST[i][id<<1]=ST[i][id<<1|1]=0;
LZ[id]=0;
}
if(x>mid) up(x,id<<1|1,mid+1,r);
else up(x,id<<1,l,mid);
for(int i=29;i>=0;i--) ST[i][id]=ST[i][id<<1]+ST[i][id<<1|1];
}
void upd (int x,int y,int id,int l,int r){
if(y<l || x>r) return;
if(x<=l && r<=y){
for(int i=0;i<29;i++)
ST[i][id]=ST[i+1][id];
ST[29][id]=0;
LZ[id]++;
return;
}
int mid=l+r>>1;
if(LZ[id]){
minn(LZ[id],30);
LZ[id<<1]+=LZ[id];
LZ[id<<1|1]+=LZ[id];
for(int i=0;i<30-LZ[id];i++) ST[i][id<<1]=ST[i+LZ[id]][id<<1],ST[i][id<<1|1]=ST[i+LZ[id]][id<<1|1];;
for(int i=30-LZ[id];i<30;i++) ST[i][id<<1]=ST[i][id<<1|1]=0;
LZ[id]=0;
}
upd(x,y,id<<1,l,mid);
upd(x,y,id<<1|1,mid+1,r);
for(int i=29;i>=0;i--) ST[i][id]=ST[i][id<<1]+ST[i][id<<1|1];
}
ll P[30];
ll get(int x,int y,int id,int l,int r){
if(y<l || x>r) return 0;
if(x<=l && r<=y){
ll res=0;
for(int i=0;i<30;i++)
res+=P[i]*ST[i][id];
return res;
}
int mid=l+r>>1;
if(LZ[id]){
minn(LZ[id],30);
LZ[id<<1]+=LZ[id];
LZ[id<<1|1]+=LZ[id];
for(int i=0;i<30-LZ[id];i++) ST[i][id<<1]=ST[i+LZ[id]][id<<1],ST[i][id<<1|1]=ST[i+LZ[id]][id<<1|1];;
for(int i=30-LZ[id];i<30;i++) ST[i][id<<1]=ST[i][id<<1|1]=0;
LZ[id]=0;
}
//for(int i=29;i>=0;i--) ST[i][id]=ST[i][id<<1]+ST[i][id<<1|1];
return get(x,y,id<<1,l,mid)+get(x,y,id<<1|1,mid+1,r);
}
ll F[MAX];
void UPD(int id,int val){
for(;id<MAX;id+=id&-id) F[id]+=val;
}
ll GET(int id){
ll res=0;
for(;id>0;id-=id&-id) res+=F[id];
return res;
}
int main() {
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//freopen("JOI15.inp", "r", stdin);//freopen("JOI15.out", "w", stdout);
int n,Q;
cin>>n>>Q>>K;
if(K==1){
for(int i=1,x;i<=n;i++){
cin>>a[i];
UPD(i,a[i]);
}
int t,x,y;
while(Q--){
cin>>t>>x>>y;
if(t==1){
UPD(x,y-a[x]);a[x]=y;
}
else{
if(t==3)
cout<<GET(y)-GET(x-1)<<'\n';
}
}
return 0;
}
P[0]=1;
for(int i=1;i<30;i++) P[i]=P[i-1]*K;
for(int i=1;i<=n;i++) {cin>>val;up(i,1,1,n);}
int t,x,y;
while(Q--){
cin>>t>>x>>y;
if(t==1){
val=y;
up(x,1,1,n);
}
else{
if(t==2)
upd(x,y,1,1,n);
else cout<<get(x,y,1,1,n)<<'\n';
}
}
}
