#include <bits/stdc++.h>
#define sz(x) (int)(x.size() )
#define ll long long
#define all(x) x.begin(),x.end()
#define CTE 30
const int MAXN = 1e5+10 ;
using namespace std ;
struct Node
{
int qtdLazy ;
long long sums[CTE] ;
Node()
{
qtdLazy = 0 ;
for(int i = 0 ; i < CTE ; i++ ) sums[i] = 0LL ;
}
} ;
struct Seg
{
Node tree[MAXN*4] ;
int m(int l, int r ) { return (l+r)>>1 ; }
void refresh(int pos, int l, int r )
{
if(tree[pos].qtdLazy == 0 ) return ;
Node &ptr = tree[pos] ;
for(int i = 0 ; i < CTE ; i++ )
{
if( i + ptr.qtdLazy < CTE )
ptr.sums[i] = ptr.sums[ i+ptr.qtdLazy ] ;
else ptr.sums[i] = 0 ;
}
if( l == r ) return (void)(ptr.qtdLazy = 0) ;
tree[pos<<1].qtdLazy += ptr.qtdLazy ;
tree[pos<<1|1].qtdLazy += ptr.qtdLazy ;
ptr.qtdLazy = 0 ;
}
void merge(Node &v, Node &l, Node &r )
{
for(int i = 0 ;i < CTE ; i++ )
v.sums[i] = l.sums[i] + r.sums[i] ;
}
//Don't forget to erase the value that was there before updating
void upd(int pos, int l, int r, int k, vector<long long> toSum )
{
refresh(pos,l,r) ;
for(int i = 0 ; i < CTE ; i++ )
tree[pos].sums[i] += toSum[i] ;
if( l == r ) return ;
if( k <= m(l,r) ) upd(pos<<1 , l, m(l,r) , k , toSum ) ;
else upd(pos<<1|1 , m(l,r)+1, r, k , toSum ) ;
}
void spray(int pos, int l, int r, int beg, int en )
{
refresh(pos,l,r) ;
if( l > en || r < beg ) return ;
if( l >= beg && r <= en )
{
tree[pos].qtdLazy++ ;
refresh(pos,l,r) ;
return ;
}
spray(pos<<1 , l ,m(l,r) , beg, en ) ;
spray(pos<<1|1 , m(l,r)+1, r, beg, en ) ;
merge( tree[pos], tree[pos<<1] , tree[pos<<1|1] ) ;
}
Node qry(int pos, int l, int r, int beg, int en )
{
if( l > en || r <beg ) return *(new Node() ) ;
refresh(pos,l,r ) ;
if( l >= beg && r <= en ) return tree[pos] ;
Node a = qry(pos<<1 ,l , m(l,r) , beg, en ) ;
Node b = qry(pos<<1|1 , m(l,r)+1, r, beg, en ) ;
Node v ;
merge(v,a,b) ;
return v ;
}
} seg ;
int n , k , q ;
long long miniBit[MAXN] ;
void upd(int i, long long val ) { for(; i < MAXN ; i += i & -i ) miniBit[i] += val ; }
long long qry(int i )
{
long long tot = 0 ;
for(; i > 0 ; i -= i &-i ) tot += miniBit[i] ;
return tot ;
}
void solve1()
{
vector<long long> plate(n+1) ;
for(int i = 1 ; i <= n ; i++ )
{
scanf("%lld", &plate[i] ) ;
upd(i, plate[i]) ;
}
for(int i = 1 , t ,l ,r ; i <= q ; i++ )
{
scanf("%d%d%d", &t, &l, &r ) ;
if(t == 1 )
{
upd( l , -plate[l] + r ) ;
plate[l] = r ;
}
else if( t == 3 ) printf("%lld\n", qry(r) - qry(l-1) ) ;
}
exit(0) ;
}
int main()
{
scanf("%d %d %d", &n, &q, &k ) ;
if(k == 1 ) solve1() ;
for(int i = 1 , c ; i <= n ; i++ )
{
vector<long long> toSum(CTE);
scanf("%lld", &toSum[0] ) ;
for(int j = 1 ; j < CTE ; j++ )
toSum[j] = toSum[j-1]/k ;
seg.upd(1,1,n, i, toSum ) ;
}
for(int i = 1 , t , l, r ; i <= q ; i++ )
{
scanf("%d %d %d", &t, &l, &r ) ;
Node ans ;
if(t == 1 )
{
ans = seg.qry(1,1,n, l , l ) ;
vector<long long> toSum(CTE) ;
toSum[0] = r ;
for(int j = 1 ; j < CTE ; j++ ) toSum[j] = toSum[j-1]/k ;
for(int j = 0 ; j < CTE ; j++ ) toSum[j] -= ans.sums[j] ;
seg.upd(1,1,n, l , toSum ) ;
}
else if( t == 2 ) seg.spray(1,1,n, l, r ) ;
else
{
ans = seg.qry(1,1,n, l, r ) ;
printf("%lld\n", ans.sums[0] ) ;
}
}
}
