#include<bits/stdc++.h>
#pragma GCC optimize("-Ofast")
//#pragma GCC optimize("trapv")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2,tune=native")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")
#define I inline void
#define S struct
#define vi vector<int>
#define vii vector<pair<int,int>>
#define pii pair<int,int>
#define pll pair<ll,ll>
using namespace std ;
using ll = long long ;
using ld = long double ;
const int N = 2e5 + 7 , mod = 1e9 + 7 ;
const ll inf = 2e18 ;
// How interesting!
int n, m , k ;
ll tree[N * 4] ;
void update(int node, int L , int R , int ix , int v){
if(L == R){
tree[node] = v ;
return ;
}
int mid = (L + R) >> 1;
if(ix <= mid)
update(node*2+1 , L , mid , ix ,v) ;
else
update(node*2+2, mid + 1 , R , ix , v) ;
tree[node] = tree[node*2+1] + tree[node*2+2] ;
}
void spray(int node , int L, int R , int l , int r){
if(l > R || r < L)
return ;
if(L == R){
tree[node]/=k ;
return ;
}
if(L >= l && R <= r && tree[node] == 0){
return ;
}
int mid = (L + R) >> 1;
spray(node * 2 + 1, L , mid, l , r) ;
spray(node * 2 + 2, mid + 1 , R , l , r) ;
tree[node] = tree[node*2+1] + tree[node*2+2] ;
}
ll query(int node, int L , int R , int l , int r){
if(l > r || l > R || r < L)
return 0 ;
if(L>= l && R <= r)
return tree[node] ;
int mid = (L + R) >> 1 ;
ll s1 = query(node*2+1, L , mid , l , r) ;
ll s2 = query(node*2+2 , mid+1 , R , l , r) ;
return s1 + s2 ;
}
int d1[N], d2[N], d3[N] ;
ll bit[N], a[N];
inline void add(int ix, ll val){for(;ix<N;ix+=ix&-ix)bit[ix]+=val ; }
ll upto(int ix){
ll ret = 0 ;
for(;ix;ix-=ix&-ix)ret+=bit[ix] ;
return ret;
}
inline ll get(int l, int r){return upto(r) - upto(l - 1) ; }
void solve1(){
for(int i = 0 ;i < m; ++ i){
if(d1[i] == 1){
add(d2[i] , d3[i] - a[d2[i]]) ;
a[d2[i]] = d3[i] ;
}else if(d1[i] == 3){
cout<< get(d2[i] , d3[i]) <<"\n" ;
}
}
}
int main(){
ios_base::sync_with_stdio(0) ;
cin.tie(0) ;
//freopen("in.in" , "r" , stdin) ;
cin >> n >> m >> k ;
for(int i= 1; i <= n; ++ i){
int x ; cin >> x ;
add(i , x) ;
a[i] = x;
update(0 , 1, N , i , x) ;
}
for(int i = 0 ; i< m ; ++ i){
cin >> d1[i] >> d2[i] >> d3[i] ;
}
if(k == 1){
solve1() ;
return 0;
}
for(int i = 0 ;i < m ; ++ i){
int t = d1[i], l = d2[i] , r = d3[i] ;
if(t == 1){
update(0 , 1, N, l , r) ;
}else if(t == 2){
if(k > 1) ;
spray(0 , 1 , N , l , r) ;
}else{
cout<< query(0 ,1 , N, l , r) <<"\n" ;
}
}
return 0 ;
}
/*
- bounds sir (segtree = 4N, eulerTour = 2N, ...)
- a variable defined twice?
- will overflow?
- is it a good complexity?
- don't mess up indices (0-indexed vs 1-indexed)
- reset everything between testcases.
*/
