#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast,unroll-loops")
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <long double, pii> muchie;
typedef tree <ll, null_type, less_equal <ll>, rb_tree_tag, tree_order_statistics_node_update> OST;
const ll NMAX = 200001;
const ll VMAX = 100001;
const ll INF = (1LL << 60);
const ll HALF = (1LL << 59);
const ll MOD = 30013;
const ll BLOCK = 318;
const ll base = 31;
const ll nr_of_bits = 21;
ll k;
class All{
public:
struct Node{
ll nrr;
ll sum;
ll maxim;
};
Node all[4 * NMAX];
ll lazy[4 * NMAX];
Node combine(Node a, Node b){
Node sol;
sol.sum = a.sum + b.sum;
sol.nrr = a.nrr + b.nrr;
sol.maxim = max(a.maxim, b.maxim);
return sol;
}
void propaga(ll node, ll st, ll dr){
if(st != dr){
lazy[node * 2] += lazy[node];
lazy[node * 2 + 1] += lazy[node];
}
if(lazy[node]){
all[node].maxim = 0;
all[node].sum = 0;
}
lazy[node] = 0;
}
void update(ll node, ll st, ll dr, ll a, ll b){
propaga(node, st, dr);
if(st == dr){
all[node] = {(b % k == 0), b, b};
return;
}
ll mid = (st + dr) / 2;
if(a <= mid){
update(node * 2, st, mid, a, b);
}else{
update(node * 2 + 1, mid + 1, dr, a, b);
}
propaga(node * 2, st, mid);
propaga(node * 2 + 1, mid + 1, dr);
all[node] = combine(all[node * 2], all[node * 2 + 1]);
}
void imparte(ll node, ll st, ll dr, ll a, ll b){
propaga(node, st, dr);
if(a <= st && dr <= b && all[node].maxim < k){
lazy[node]++;
return;
}
if(st == dr){
all[node].maxim /= k;
all[node].sum = all[node].maxim;
return;
}
ll mid = (st + dr) / 2;
if(a <= mid){
imparte(node * 2, st, mid, a, b);
}
if(b > mid){
imparte(node * 2 + 1, mid + 1, dr, a, b);
}
propaga(node * 2, st, mid);
propaga(node * 2 + 1, mid + 1, dr);
all[node] = combine(all[node * 2], all[node * 2 + 1]);
}
ll query(ll node, ll st, ll dr, ll a, ll b){
propaga(node, st, dr);
if(a <= st && dr <= b)
return all[node].sum;
ll mid = (st + dr) / 2;
ll s = 0;
if(a <= mid)
s += query(node * 2, st, mid, a, b);
if(b > mid)
s += query(node * 2 + 1, mid + 1, dr, a, b);
return s;
}
}st;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll n, q, i;
cin >> n >> q >> k;
for(i = 1; i <= n; i++){
ll x;
cin >> x;
st.update(1, 1, n, i, x);
}
while(q--){
ll c, l, r;
cin >> c >> l >> r;
if(c == 1){
st.update(1, 1, n, l, r);
}else if(c == 2){
st.imparte(1, 1, n, l, r);
}else{
cout << st.query(1, 1, n, l, r) << "\n";
}
}
return 0;
}
