#include<bits/stdc++.h>
using namespace std;
#define int long long
const int T = 131072;
const int NB_SEGTREE = 32;
const int INF = 1e18+42;
void upd(int nde, vector<int>& ab)
{
ab[nde] = ab[nde*2] + ab[nde*2 +1];
if(nde > 1)
upd(nde/2, ab);
}
void setValue(int pos, int value, vector<int>& ab)
{
ab[pos + T] = value;
upd((pos + T)/2, ab);
}
int query(int nde, int RB, int RE, int GB, int GE, vector<int>& ab)
{
if(RB > GE || RE < GB)
return 0;
if(RB >= GB && RE <= GE)
return ab[nde];
int mid = (RB + RE)/2;
return query(nde*2, RB, mid, GB, GE, ab) + query(nde*2 +1, mid+1, RE, GB, GE, ab);
}
signed main()
{
int ctr = 0;
int N, Q, K;
scanf("%lld%lld%lld", &N, &Q, &K);
vector<vector<int > > ABs(NB_SEGTREE, vector<int>(2*T, 0));
for(int iN = 0; iN < N; iN++)
{
int value;
scanf("%lld", &value);
setValue(iN, value, ABs[0]);
}
set<pair<int, int>> debInterSet; // posi, prof;
debInterSet.insert({0, 0});
debInterSet.insert({N, -1});
for(int iQ = 0; iQ < Q; iQ++)
{
int type, Ti, Ui;
scanf("%lld%lld%lld", &type, &Ti, &Ui);
//printf("%lld %lld %lld\n", type, Ti, Ui);
if(type == 1)
{
int id = Ti, newValue = Ui;
id--;
auto it = debInterSet.upper_bound(pair<int, int>(id, +INF));
int finInterEx = (*(it)).first;
it--;
int debInter = (*(it)).first;
int profInter = (*(it)).second;
int newProf = 0;
if(id+1 <finInterEx)
debInterSet.insert({id+1, profInter});
if(debInter == id)
debInterSet.erase(it);
debInterSet.insert({id, newProf});
setValue(id, 0, ABs[profInter]);
setValue(id, newValue, ABs[0]);
}
else if(type == 2)
{
if(K!=1)
{
int l = Ti, r = Ui;
l--; r--;
while (l <= r)
{
auto itAfter = debInterSet.upper_bound(pair<int, int>(l, +INF));
auto itBefore = debInterSet.upper_bound(pair<int, int>(l, +INF));
itBefore--;
int finInterEx = (*(itAfter)).first;
int profNextCheck = (*(itAfter)).second;
int debInter = (*(itBefore)).first;
int profInter = (*(itBefore)).second;
while (profNextCheck == profInter)
{
auto itsuppr = debInterSet.upper_bound(pair<int, int>(l, +INF));
debInterSet.erase(itsuppr);
itAfter = debInterSet.upper_bound(pair<int, int>(l, +INF));
finInterEx = (*(itAfter)).first;
profNextCheck = (*(itAfter)).second;
}
int newProf = profInter+1;
if(profInter == NB_SEGTREE-1)
{
l = min(finInterEx, r+1);
continue;
}
if(r+1 <finInterEx)
debInterSet.insert({r+1, profInter});
if(debInter == l)
debInterSet.erase(itBefore);
debInterSet.insert({l, newProf});
for(int pt = l; pt <min(finInterEx, r+1); pt++)
{
ctr ++;
int valuePt = ABs[profInter][pt+T];
setValue(pt, 0, ABs[profInter]);
setValue(pt, valuePt/K, ABs[newProf]);
}
l = min(finInterEx, r+1);
}
}
}
else if(type == 3)
{
int l = Ti, r = Ui;
l--; r--;
int res = 0;
for(int iAB = 0; iAB < NB_SEGTREE; iAB++)
{
res += query(1, 0, T-1, l, r, ABs[iAB]);
}
printf("%lld\n", res);
}
/*printf("%lld\n", ctr);
for(auto v : debInterSet)
{
printf("%lld/%lld - ", v.first, v.second);
}
printf("\n");*/
}
}
