#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
using ll = long long;
const ll mod=1e9+7;
const int nx=1e5+5;
deque<ll> operator +(deque<ll> a, deque<ll> b)
{
deque<ll> c;
int l=a.size(), r=b.size();
c.resize(max(l, r));
while(a.size()<c.size()) a.push_back(0);
while(b.size()<c.size()) b.push_back(0);
for(int i = 0; i < c.size(); i++)
c[i]=a[i]+b[i];
return c;
}
int n, q, k, a[nx], la[nx<<2];
deque<ll> nod[nx<<2];
void build(int id, int l, int r)
{
la[id]=0;
if(l==r)
{
nod[id].clear();
while(a[l]>0) nod[id].push_back(a[l]), a[l]/=k;
return;
}
int mid=(l+r)>>1;
build(id<<1, l, mid);
build(id<<1|1, mid+1, r);
nod[id]=nod[id<<1]+nod[id<<1|1];
}
void down(int id)
{
if(!la[id]) return;
for(int te = 1; te <= la[id]; te++)
{
for(int j = id*2; j <= id*2+1; j++)
{
la[j]++;
if(nod[j].size()) nod[j].pop_front();
}
}
la[id]=0;
}
void upd(int id, int l, int r, int p, int val)
{
if(l>p || r<p) return;
if(l==r)
{
nod[id].clear();
while(val>0) nod[id].push_back(val), val/=k;
return;
}
int mid=(l+r)>>1;
down(id);
upd(id<<1, l, mid, p, val);
upd(id<<1|1, mid+1, r, p, val);
nod[id]=nod[id<<1]+nod[id<<1|1];
}
void update(int id, int l, int r, int u, int v)
{
if(l>v || r<u) return;
if(l>=u && r<=v)
{
if(nod[id].size()) nod[id].pop_front();
la[id]++;
return;
}
int mid=(l+r)>>1;
down(id);
update(id<<1, l, mid, u, v);
update(id<<1|1, mid+1, r, u, v);
nod[id]=nod[id<<1]+nod[id<<1|1];
}
ll get(int id, int l, int r, int u, int v)
{
if(l>v || r<u) return 0;
if(l>=u && r<=v) return (nod[id].empty())?0:nod[id].front();
int mid=(l+r)>>1;
down(id);
return get(id<<1, l, mid, u, v)+get(id<<1|1, mid+1, r, u, v);
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin>>n>>q>>k;
for(int i = 1; i <= n; i++)
cin>>a[i];
build(1, 1, n);
while(q--)
{
int e, x, y;
cin>>e>>x>>y;
if(e==1) upd(1, 1, n, x, y);
else if(e==2) update(1, 1, n, x, y);
else cout<<get(1, 1, n, x, y)<<'\n';
}
}
