#include <bits/stdc++.h>
using namespace std;



int n,m,p;
int q[18][500005];
int t[18][500000];
int a[100005];
int sz;


inline void push(int x,int y,int l,int r) {
    q[y][x+x]^=q[y][x];
    q[y][x+x+1]^=q[y][x];
    q[y][x]=0;
    int mid=(l+r)>>1;
    t[y][x+x]=mid-l+1-t[y][x+x];
    t[y][x+x+1]=r-mid-t[y][x+x+1];
}

void update(int l,int r,int ll,int rr,int x,int y) {
    if (l>r || ll>r || l>rr || ll>rr) return;
    if (l>=ll && r<=rr) {
        q[y][x]^=1;
        t[y][x]=r-l+1-t[y][x];
        return;
    }
    int mid=(l+r)>>1;
    if (q[y][x]) push(x,y,l,r);
    update(l,mid,ll,rr,x+x,y);
    update(mid+1,r,ll,rr,x+x+1,y);
    t[y][x]=t[y][x+x]+t[y][x+x+1];
}


inline void update1(int x,int y,int z) {
    int l=x-p+1;
    int r=min(n-p+1,x);
    if (l>r) return;
    bool t1,t2;
    for (int i=0;i<17;++i) {
        t1=t2=false;
        if (y&(1<<i)) t1=true;
        if (z&(1<<i)) t2=true;
        if (t1!=t2) update(1,sz,l,r,1,i);
    }
}



int get(int l,int r,int ll,int rr,int x,int y) {
    if (l>r || ll>r || l>rr || ll>rr) return 0;
    if (l>=ll && r<=rr) return t[y][x];
    int mid=(l+r)>>1;
    if (q[y][x]) push(x,y,l,r);
    return get(l,mid,ll,rr,x+x,y)+get(mid+1,r,ll,rr,x+x+1,y);
}

inline long long solve(int l,int r) {
    long long res=0;
    long long cur;
    for (int i=0;i<17;++i) {
        cur=get(1,sz,l,r,1,i);
        res+=cur*1ll*(1<<i);
    }
    return res;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n>>m>>p;
    for(int i=1;i<=n;++i) {
        cin>>a[i];
    }
    sz=1;
    while (sz<n) sz+=sz;
    for (int i=1;i<=n;++i) {
        update1(i,0,a[i]);
    }
    int tp,x,y;
    while (m--) {
        cin>>tp>>x>>y;
        if (tp==1) {
            update1(x,a[x],(a[x]^y));
            a[x]^=y;
        } else {
            cout<<solve(x,y)<<'\n';
        }
    }

}