#include <bits/stdc++.h>
#define maxn (int)(1e5+51)
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define ll long long
#define pb push_back
#define ull unsigned long long
#define ii pair<int,int>
#define iii tuple<int,int,int>
#define inf 2000000001
#define mod 1000000007 //998244353
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }
pair<ii,vector<ll>>lazy[4*maxn];
int n,q;
ll k;
ll v[maxn],seg[4*maxn];
void build(int i,int l,int r){
if(l==r){
seg[i] = v[l];
ll tmp = v[l];
while(true&&k!=1){lazy[i].second.pb(tmp/k);if(!(tmp/k))break;tmp/=k;}
lazy[i].first={-1,0};
return;
}
int md = (l+r)/2;
build(2*i,l,md);
build(2*i+1,md+1,r);
seg[i] = seg[2*i] + seg[2*i+1];
int j = 0;
while(true&&k!=1){
int le = (j>=sz(lazy[2*i].second) ? 0 : lazy[2*i].second[j]);
int ri = (j>=sz(lazy[2*i+1].second) ? 0 : lazy[2*i+1].second[j++]);
lazy[i].second.pb(le+ri);
if(le+ri==0)break;
}
lazy[i].first={-1,0};
}
void push(int i,int l,int r){
if(k==1)return;
auto [ind,add] = lazy[i].first;
if(!add)return;
ind = min(sz(lazy[i].second)-1,ind+add);
seg[i] = lazy[i].second[ind];
lazy[i].first.second = 0;
if(l==r)return;
lazy[2*i].first.second+=add;
lazy[2*i+1].first.second+=add;
}
void update(int i,int l,int r,int x,int d){
if(k!=1)push(i,l,r);
if(l>x||r<x)return;
if(l==r){
seg[i] = d;
lazy[i].second.clear();
ll tmp = d;
while(true&&k!=1){lazy[i].second.pb(tmp/k);if(!(tmp/k))break;tmp/=k;}
lazy[i].first={-1,0};
return;
}
int md = (l+r)/2;
update(2*i,l,md,x,d);
update(2*i+1,md+1,r,x,d);
lazy[i].second.clear();
int j = 0;
while(true&&k!=1){
int le = (j>=sz(lazy[2*i].second) ? 0 : lazy[2*i].second[j]);
int ri = (j>=sz(lazy[2*i+1].second) ? 0 : lazy[2*i+1].second[j++]);
lazy[i].second.pb(le+ri);
if(le+ri==0)break;
}
seg[i] = seg[2*i] + seg[2*i+1];
lazy[i].first={-1,0};
}
void update2(int i,int l,int r,int x,int y){
if(k!=1)push(i,l,r);
if(l>y||r<x)return;
if(x<=l&&r<=y){
lazy[i].first.second++;
push(i,l,r);
return;
}
int md = (l+r)/2;
update2(2*i,l,md,x,y);
update2(2*i+1,md+1,r,x,y);
seg[i] = seg[2*i] + seg[2*i+1];
}
ll query(int i,int l,int r,int x,int y){
if(k!=1)push(i,l,r);
if(l>y||r<x)return 0;
if(x<=l&&r<=y)return seg[i];
int md = (l+r)/2;
return query(2*i,l,md,x,y) + query(2*i+1,md+1,r,x,y);
}
void debug(int i,int l,int r){
if(l==r){
cout<<l<<" "<<r<<" "<<seg[i]<<endl;return;
}
int md = (l+r)/2;
debug(2*i,l,md);
debug(2*i+1,md+1,r);
cout<<l<<" "<<r<<" "<<seg[i]<<endl;
}
int main(){_
cin>>n>>q>>k;
for(int i=1;i<=n;i++)cin>>v[i];
vector<ll>x = {1,2,3,4};
build(1,1,n);
while(q--){
int t,a,b;cin>>t>>a>>b;
if(t==1){
update(1,1,n,a,b);
}else if(t==2){
if(k!=1)update2(1,1,n,a,b);
}else{
cout<<query(1,1,n,a,b)<<endl;
}
}
}
