#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define xx first
#define yy second
#define pb push_back
#define MAXN 100010
using namespace std;
int n, q, k;
ll a[MAXN], bit[MAXN];
set<int> koji;
void upd(int x, ll v)
{
while (x<MAXN)
{
bit[x]+=v;
x+=x&(-x);
}
}
ll sum(int x)
{
ll ret=0;
while (x)
{
ret+=bit[x];
x-=x&(-x);
}
return ret;
}
int main()
{
cin>>n>>q>>k;
for (int i=1; i<=n; i++) { cin>>a[i]; upd(i, a[i]); if (a[i]) koji.insert(i); }
while (q--)
{
int t; cin>>t;
if (t==1)
{
ll x, v; cin>>x>>v;
upd(x, v-a[x]);
if (v) koji.insert(x);
a[x]=v;
}
else if (t==2)
{
int l, r; cin>>l>>r;
if (k==1) continue;
for (auto it=koji.lower_bound(l); it!=koji.end() && (*it)<=r; it++)
{
int x=*it;
//cout<<x<<" ala "<<a[x]<<endl;
if (a[x]==0) continue;
upd(x, a[x]/k-a[x]);
a[x]/=k;
}
for (auto it=koji.lower_bound(l); it!=koji.end() && (*it)<=r; it++)
{
int x=*it;
if (a[x]==0) koji.erase(it);
}
}
else
{
int l, r; cin>>l>>r;
cout<<sum(r)-sum(l-1)<<endl;
}
/*for (int i=1; i<=n; i++) cout<<a[i]<<" ";
cout<<endl;
for (auto it:koji) cout<<(it)<<" ";
cout<<endl;*/
}
}
