#include <bits/stdc++.h>
#define fi first
#define se second
#define pp pop_back
#define ll long long
#define pb push_back
#define ld long double
#define debug cout << "OK\n";
#define all(x) x.begin(), x.end()
#define mp make_pair
using namespace std;
const ll N = 1e6 + 200;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ll pe = mod2;
const ll pe2 = 570210983;
const ld eps = 1e-6;
/*
Rucode: jaqVYNrpMj
JUDGE_ID: 295965SY
dl:160532
*/
void data() {
#ifdef NURS
freopen("main.in", "r", stdin);
freopen("main.out", "w", stdout);
#endif
}
void speed_force() {
ios_base::sync_with_stdio(0),
cin.tie(0),cout.tie(0);
}
int n, q, k;
ll a[N];
ll f[N];
int type;
void upd(int pos, ll val)
{
for (int i = pos; i <= n; i |= (i + 1))
{
f[i] += val;
}
}
ll get(int pos)
{
ll res = 0;
for (int i = pos; i >= 1; i = (i & (i + 1)) - 1)
{
res += f[i];
}
return res;
}
int main()
{
data();
cin >> n >> q >> k;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
upd(i, a[i]);
}
//subtask 3
if (k == 1)
{
for (int i = 1; i <= q; i++)
{
cin >> type;
if (type == 1)
{
int pos, x;
cin >> pos >> x;
upd(pos, -a[pos]);
a[pos] = x;
upd(pos, x);
}
else if (type == 2)
{
int l, r;
cin >> l >> r;
}
else
{
int l, r;
cin >> l >> r;
cout << get(r) - get(l - 1) << '\n';
}
}
return 0;
}
//subtask 1
for (int i = 1; i <= q; i++)
{
cin >> type;
if (type == 1)
{
int pos, x;
cin >> pos >> x;
upd(pos, -a[pos]);
a[pos] = x;
upd(pos, x);
}
else if (type == 2)
{
int l, r;
cin >> l >> r;
for (int j = l; j <= r; j++)
{
upd(j, -a[j]);
upd(j, a[j] / k);
a[j] /= k;
}
}
else
{
int l, r;
cin >> l >> r;
cout << get(r) - get(l - 1) << '\n';
}
}
}
/*
*/
