/*
*/

#pragma GCC optimize("O3")
#define _CRT_SECURE_NO_WARNINGS
#include <fstream>
#include <iostream>
#include <string>
#include <complex>
#include <math.h>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <stdio.h>
#include <stack>
#include <algorithm>
#include <list>
#include <ctime>

#include <memory.h>
#include <assert.h>

#define y0 sdkfaslhagaklsldk

#define y1 aasdfasdfasdf
#define yn askfhwqriuperikldjk
#define j1 assdgsdgasghsf
#define tm sdfjahlfasfh
#define lr asgasgash
#define norm asdfasdgasdgsd
#define have adsgagshdshfhds
#define ends asdgahhfdsfshdshfd

#define eps 1e-8
#define M_PI 3.141592653589793
#define bsize 512

#define ldouble long double
using namespace std;

#define bs 998244353

const int N = 1200031;

long long n,m,p,ar[N],tp;
long long f[N];

long long suf_xor[N];

pair<int,int> get_inter(int l1,int r1,int l2,int r2){
	return make_pair(max(l1,l2),min(r1,r2));
}

long long t[1<<20][20],toxor[1<<20][20];

void build(int v,int tl,int tr){

	if (tl==tr){
		for (int i=0;i<20;i++){
			t[v][i]=((f[tl]>>i)&1);
		}
		return;
	}
	int tm=tl+tr;
	tm/=2;
	build(v*2,tl,tm);
	build(v*2+1,tm+1,tr);
	for (int i=0;i<20;i++){
		t[v][i]=t[v*2][i]+t[v*2+1][i];
	}
}

void make_flip(int v,int l,int r,int ps){
	toxor[v][ps]^=1;
	t[v][ps]=(r-l+1)-t[v][ps];
}

void push(int v,int tl,int tr){
	int tm=tl+tr;
	tm/=2;
	for (int i=0;i<20;i++){
		if (toxor[v][i]){
			make_flip(v*2,tl,tm,i);
			make_flip(v*2+1,tm+1,tr,i);
			toxor[v][i]=0;
		}
	}
}

long long get(int v,int tl,int tr,int l,int r){

	if (l>r)
		return 0;
	if (tl==l&&tr==r){
		long long res=0;
		for (int i=0;i<20;i++){
			res+=t[v][i]*(1<<i);
		}
		return res;
	}
	push(v,tl,tr);
	int tm=tl+tr;
	tm/=2;
	return get(v*2,tl,tm,l,min(r,tm))+get(v*2+1,tm+1,tr,max(tm+1,l),r);
}

void apply(int v,int l,int r,int val){
	for (int i=0;i<20;i++){
		if (val&(1<<i)){
			toxor[v][i]^=1;
			t[v][i]=(r-l+1)-t[v][i];
		}
	}
}

void update(int v,int tl,int tr,int l,int r,int val){
	if (l>r)
		return;
	if (tl==l&&tr==r){
		apply(v,l,r,val);
		return;
	}
	push(v,tl,tr);
	int tm=tl+tr;
	tm/=2;
	update(v*2,tl,tm,l,min(r,tm),val);
	update(v*2+1,tm+1,tr,max(tm+1,l),r,val);
	for (int i=0;i<20;i++){
		t[v][i]=t[v*2][i]+t[v*2+1][i];
	}
}

int main(){
//	freopen("apache.in","r",stdin);
//	freopen("apache.out","w",stdout);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	ios_base::sync_with_stdio(0);
//	cin.tie(0);

	cin>>n>>m>>p;

	for (int i=1;i<=n;i++){
		cin>>ar[i];
	}

	for (int i=n;i;--i){
		suf_xor[i]=(suf_xor[i+1]^ar[i]);
	}

	for (int i=1;i<=n;i++){
		if (i+p-1<=n){
			f[i]=suf_xor[i+p]^suf_xor[i];
		}
	}

	build(1,1,n);

	for (int i=1;i<=m;i++){
		cin>>tp;
		if (tp==1){
			int a,b;
			cin>>a>>b;
			pair<int,int> seg=get_inter(1,n-p+1,a-p+1,a);
			update(1,1,n,seg.first,seg.second,b);
		}
		else
		{
			int l,r;
			cin>>l>>r;
			long long res=get(1,1,n,l,r);
			cout<<res<<endl;
		}
	}

//	cin.get(); cin.get();
	return 0;
}