#include <bits/stdc++.h>
using namespace std;
int const N = 100005;
long long seg[4*N];
long long c[N];
int n;
void cx(int x, long long v, int l=1, int r=n, int pos=1)
{
if(l == r)
{
seg[pos]= v;
return;
}
int m = (l+r)/2;
if(x <= m)
{
cx(x, v, l, m, pos*2);
}
else
{
cx(x, v, m+1, r,pos*2+1);
}
seg[pos]=seg[pos*2]+seg[pos*2+1];
}
long long get(int curl, int curr, int l=1, int r=n, int pos=1)
{
if(seg[pos]==0)return 0;
if(r < curl)
{
return 0;
}
if(l > curr)
{
return 0;
}
if(curr>=r && curl<=l)
{
return seg[pos];
}
int m = (l+r)/2;
long long rez=0;
rez+=get(curl, curr, l, m, pos*2)+get(curl, curr, m+1, r, pos*2+1);
return rez;
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int q, k;
cin >> n >> q >> k;
set<int> vn;
for(int i =1; i <= n; i++)
{
cin >> c[i];
cx(i, c[i]);
if(c[i]) vn.insert(i);
}
while(q--)
{
int s; cin >> s;
if(s==1)
{
long long a, b; cin >> a >> b;
c[a]=b;
if(c[a]) vn.insert(a);
else if(b==0 && vn.count(a)) vn.erase(a);
cx(a, b);
}
if(s==2)
{
int l, r; cin >> l >> r;
if(k==1)continue;
for(auto i = vn.lower_bound(l); i!= vn.end();)
{
// cout << *i << "\n";
if(*i > r)break;
c[*i]/=3;
cx(*i, c[*i]);
if(c[*i]==0){
vn.erase(*i);
i = vn.lower_bound( l);
}
else
{
i++;
l=*i+1;
}
}
}
if(s==3)
{
int l,r ; cin >> l >> r;
cout << get(l,r) << "\n";
}
}
return 0;
}
