#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 t[N * 4], m[N * 4];
void upd2(int pos, int val, int v = 1, int tl = 1, int tr = n)
{
if (tl == tr)
{
t[v] = val;
return;
}
int tm = (tl + tr) / 2;
if (pos <= tm)
upd2(pos, val, v * 2, tl, tm);
else
upd2(pos, val, v * 2 + 1, tm + 1, tr);
t[v] = t[v * 2] + t[v * 2 + 1];
}
void push(int v, int tl, int tr)
{
if (m[v])
{
t[v * 2] = t[v];
t[v * 2 + 1] = t[v];
m[v * 2] = m[v];
m[v * 2 + 1] = m[v];
}
}
int get3(int l, int r, int v = 1, int tl = 1, int tr = n)
{
push(v, tl, tr);
if (l <= tl && tr <= r)
return t[v];
if (l > tl || r < tl)
return 0;
int tm = (tl + tr) / 2;
return get3(l, r, v * 2, tl, tm) + get3(l, r, v * 2 + 1, tm + 1, tr);
}
void get2(int l, int r, int v = 1, int tl = 1, int tr = n)
{
push(v, tl, tr);
if (l <= tl && tr <= r)
{
m[v] = 1;
t[v] = 0;
push(v, tl, tr);
return;
}
if (l > tr || r < tl)
return;
int tm = (tl + tr) / 2;
get2(l, r, v * 2, tl, tm);
get2(l, r, v * 2 + 1, tm + 1, tr);
}
int main()
{
data();
cin >> n >> q >> k;
int check = 0;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
upd(i, a[i]);
upd2(i, a[i]);
check = (check | (a[i] > 1));
}
//subtask 3
if (check == 0)
{
for (int i = 1; i <= q; i++)
{
cin >> type;
if (type == 1)
{
int pos, x;
cin >> pos >> x;
a[pos] = x;
upd2(pos, x);
}
else if (type == 2)
{
int l, r;
cin >> l >> r;
get2(l, r);
}
else
{
int l, r;
cin >> l >> r;
cout << get3(l, r) << '\n';
}
}
return 0;
}
//subtask 2
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';
}
}
}
/*
*/
