#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#define fio ios_base::sync_with_stdio(0);cin.tie(0);
#define ll long long
#define ld long double
#define en exit(0);
#define pb push_back
#define fi first
#define se second
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N = 1e5 + 5;
ll segt[4 * N];
int c[N], n;
void upd(int p, int v, int l = 1, int r = n, int pos = 1)
{
if(l == r)
segt[pos] = v;
else
{
int mid = (l + r) / 2;
if(p <= mid)
upd(p, v, l, mid, pos * 2);
else
upd(p, v, mid + 1, r, pos * 2 + 1);
segt[pos] = segt[pos * 2] + segt[pos * 2 + 1];
}
}
ll getsum(int lb, int rb, int l = 1, int r = n, int pos = 1)
{
if(rb < l || r < lb)
return 0;
if(lb <= l && r <= rb)
return segt[pos];
int mid = (l + r) / 2;
return getsum(lb, rb, l, mid, pos * 2) + getsum(lb, rb, mid + 1, r, pos * 2 + 1);
}
int main()
{
fio
// ifstream cin("in.in");
int q, k;
cin >> n >> q >> k;
set<int> not0;
for(int i = 1;i <= n;i++)
{
cin >> c[i];
upd(i, c[i]);
if(c[i] != 0)
not0.insert(i);
}
while(q--)
{
int t;
cin >> t;
if(t == 1)
{
int p, v;
cin >> p >> v;
if(not0.count(p))
not0.erase(p);
upd(p, v);
c[p] = v;
if(v != 0)
not0.insert(p);
}
else if(t == 2)
{
int l, r;
cin >> l >> r;
if(k > 1)
{
auto t = not0.lower_bound(l);
vector<int> idx;
while(t != not0.end() && *t <= r)
{
int id = *t;
c[id] /= k;
upd(id, c[id]);
not0.erase(t);
idx.pb(id);
t = not0.lower_bound(l);
}
for(auto x : idx)
if(c[x] != 0)
not0.insert(x);
}
}
else
{
int l, r;
cin >> l >> r;
cout << getsum(l, r) << "\n";
}
}
return 0;
}
