/* I can do this all day */
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair < int, int > pii;
typedef pair < ll, ll > pll;
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define Mp make_pair
#define point complex
#define endl '\n'
#define SZ(x) (int)x.size()
#define fast_io ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define file_io freopen("input.txt", "r+", stdin); freopen("output.txt", "w+", stdout);
#define mashtali return cout << "Hello, World!", 0;
const int N = 1e6 + 10;
const int LOG = 20;
const ll mod = 1e9 + 7;
const ll inf = 8e18;
const double pi = acos(-1);
const ld eps = 1e-18;
const ld one = 1.;
ll pw(ll a, ll b, ll M, ll ret = 1) { if(a == 0) return 0; a %= M; while(b) { ret = (b & 1? ret * a % M : ret), a = a * a % M, b >>= 1; } return ret % M; }
mt19937 rng(time(nullptr));
int n, q, k, A[N];
pii seg[N << 2];
ll sum[N << 2];
void build(int v = 1, int tl = 1, int tr = n)
{
if(tl == tr)
{
seg[v] = {A[tl], tl};
sum[v] = A[tl];
return;
}
int mid = (tl + tr) >> 1;
build(v << 1, tl, mid), build(v << 1 | 1, mid + 1, tr);
seg[v] = max(seg[v << 1], seg[v << 1 | 1]);
sum[v] = sum[v << 1] + sum[v << 1 | 1];
}
void upd(int p, int x, int v = 1, int tl = 1, int tr = n)
{
if(tl == tr)
{
seg[v] = Mp(x, tl);
sum[v] = x;
return;
}
int mid = (tl + tr) >> 1;
if(p <= mid) upd(p, x, v << 1, tl, mid);
else upd(p, x, v << 1 | 1, mid + 1, tr);
seg[v] = max(seg[v << 1], seg[v << 1 | 1]);
sum[v] = sum[v << 1] + sum[v << 1 | 1];
}
ll get(int l, int r, int v = 1, int tl = 1, int tr = n)
{
if(l > tr || r < tl || l > r) return 0;
if(l <= tl && tr <= r) return sum[v];
int mid = (tl + tr) >> 1;
return get(l, r, v << 1, tl, mid) + get(l, r, v << 1 | 1, mid + 1, tr);
}
pii ask(int l, int r, int v = 1, int tl = 1, int tr = n)
{
if(l > tr || r < tl || l > r) return {-1, -1};
if(l <= tl && tr <= r)
{
return seg[v];
}
int mid = (tl + tr) >> 1;
return max(ask(l, r, v << 1, tl, mid), ask(l, r, v << 1 | 1, mid + 1, tr));
}
int main()
{
fast_io;
cin >> n >> q >> k;
for(int i = 1; i <= n; i ++)
{
cin >> A[i];
}
build();
for(int j = 1; j <= q; j ++)
{
int tp, fir, sec;
cin >> tp >> fir >> sec;
if(tp == 1)
{
A[fir] = sec;
upd(fir, sec);
}
if(tp == 2)
{
pii cu;
vector < int > pos;
while((cu = ask(fir, sec)).F > 0)
{
A[cu.S] /= k;
upd(cu.S, 0);
pos.push_back(cu.S);
}
for(auto x : pos)
{
upd(x, A[x]);
}
}
if(tp == 3)
{
cout << get(fir, sec) << endl;
}
/*printf("j = %d\n", j);
for(int i = 1; i <= n; i ++)
{
printf("%d ", A[i]);
}
printf("\n");
*/
}
return 0;
}
/* check corner case(n = 1?), watch for negetive index or overflow */
