#include <bits/stdc++.h>
using namespace std;
long long seg[400005], a[100005];
int n, q, k;
set<int> s;
void build(int i, int l, int r)
{
if (l==r)
{
seg[i]=a[l];
if (a[l])
{
s.insert(l);
// cout << "insert " << l << '\n';
}
return;
}
int mid=(l+r)/2;
build(i*2, l, mid);
build(i*2+1, mid+1, r);
seg[i]=seg[i*2]+seg[i*2+1];
}
void update(int i, int l, int r, int y, int z)
{
if (l==r)
{
seg[i]=a[y]=z;
// cout << "delete " << y << '\n';
// s.erase(y);
// if (z)
// {
// s.insert(y);
//// cout << "insert " << y << '\n';
// }
return;
}
int mid=(l+r)/2;
if (y<=mid)
update(i*2, l, mid, y, z);
else
update(i*2+1, mid+1, r, y, z);
seg[i]=seg[i*2]+seg[i*2+1];
}
long long query(int i, int l, int r, int y, int z)
{
if (y<=l && r<=z)
return seg[i];
int mid=(l+r)/2;
long long res=0;
if (l<=z && y<=mid)
res+=query(i*2, l, mid, y, z);
if (mid+1<=z && y<=r)
res+=query(i*2+1, mid+1, r, y, z);
return res;
}
int main()
{
ios::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--)
{
// cout << "q=" << q << '\n';
int x, y, z;
cin >> x >> y >> z;
if (x==1)
{
update(1, 1, n, y, z);
s.erase(y);
if (z)
s.insert(y);
}
else if (x==2)
{
if (k>=2)
{
auto itr=s.lower_bound(y);
while (itr!=s.end() && (*itr)<=z)
{
int i=*itr;
// cout << "i = " << i << '\n';
update(1, 1, n, i, a[i]/k);
itr++;
if (!a[i])
s.erase(i);
// cout << "updated a[" << i << "] to " << a[i] << '\n';
// if (a[i])
// {
//// cout << "s: ";
//// for (int iii:s)
//// cout << iii << ' ';
//// cout << '\n';
//// cout << "itr was pointing at " << (*itr) << '\n';
// if ((*itr)==(*s.rbegin()))
// break;
// itr++;
// }
// else
// {
// itr=s.lower_bound(i);
//// if(i==4)
//// cout << "i am 4\n";
// }
// cout << "s: ";
// for (int i:s)
// cout << i << ' ';
// cout << '\n';
}
}
}
else
cout << query(1, 1, n, y, z) << '\n';
// for (int i=1; i<=n; i++)
// cout << a[i] << ' ';
// cout << '\n';
// cout << "s: ";
// for (int i:s)
// cout << i << ' ';
// cout << '\n';
}
return 0;
}
