#include <bits/stdc++.h>
using namespace std;
const int N = 100001;
int n;
int k;
long long t[N*4];
void upd_plus(int i, int value, int l = 1, int r = n, int pos = 1){
int mid = (l+r)/2;
if(l == r){
t[pos] = value;
return;
}
if (mid >= i){
upd_plus(i, value, l, mid, pos*2);
}
else if (mid < i){
upd_plus(i, value, mid+1, r, pos*2+1);
}
t[pos] = t[pos*2]+t[pos*2+1];
}
void upd_div(int i, int l = 1, int r = n, int pos = 1){
int mid = (l+r)/2;
if(l == r){
t[pos] /= k;
return;
}
if (mid >= i){
upd_div(i, l, mid, pos*2);
}
else if (mid < i){
upd_div(i, mid+1, r, pos*2+1);
}
t[pos] = t[pos*2]+t[pos*2+1];
}
long long find_sum(int lb,int rb, int l = 1, int r = n, int pos = 1){
if(lb>r || rb<l){
return 0;
}
if(l>=lb && r<=rb){
return t[pos];
}
int mid = (l+r)/2;
return find_sum(lb, rb, l, mid, pos*2) + find_sum(lb,rb, mid+1, r, pos*2+1);
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(nullptr);
int q; cin >> n >> q >> k;
int c[n+1];
bool allC = true;
set<int> sPos;
set<int> notZero;
for(int i = 1; i <= n; i++){
cin >> c[i];
if(c[i] >= 2)
allC = false;
upd_plus(i, c[i]);
if(c[i]==1)
sPos.insert(i);
if(c[i]!=0)
notZero.insert(i);
}
/*
if(k==1){
while(q--){
int s; cin >> s;
if(s==1){
int a, b; cin >> a >> b;
upd_plus(a,b);
}
else if (s==2){
int l, r;
cin >> l >> r;
}
else if (s==3){
int l, r; cin >> l >> r;
cout << find_sum(l,r) << '\n';
}
}
return 0;
}
if(n<=3000 && q<=3000){
while(q--){
int s; cin >> s;
if(s==1){
int a, b; cin >> a >> b;
upd_plus(a,b);
}
else if (s==2){
int l, r; cin >> l >> r;
for(int i = l; i <= r; i++){
upd_div(i);
}
}
else{
int l, r; cin >> l >> r;
cout << find_sum(l,r) << '\n';
}
}
return 0;
}
if(allC){
while(q--){
int s; cin >> s;
if(s==1){
int a, b; cin >> a >> b;
upd_plus(a,b);
if(b==0){
sPos.erase(a);
}
else{
sPos.insert(a);
}
}
else if (s==2){
int l, r; cin >> l >> r;
auto it = sPos.lower_bound(l);
while(it != sPos.end() && *it <= r){
upd_plus(*it, 0);
sPos.erase(it);
it = sPos.lower_bound(l);
}
}
else{
int l, r; cin >> l >> r;
cout << find_sum(l,r) << '\n';
}
}
return 0;
}
*/
while(q--){
int s; cin >> s;
if(s==1){
int a, b; cin >> a >> b;
upd_plus(a,b);
if(b==0){
notZero.erase(a);
}
else{
notZero.insert(a);
}
}
else if (s==2){
int l, r; cin >> l >> r;
auto it = notZero.lower_bound(l);
while(it != notZero.end() && *it <= r){
upd_div(*it);
if(find_sum(*it,*it)==0){
notZero.erase(it);
l=*it;
}
else
l = *it+1;
it = notZero.lower_bound(l);
}
}
else{
int l, r; cin >> l >> r;
cout << find_sum(l,r) << '\n';
}
}
return 0;
}
