不是哥们

#include<bits/stdc++.h>
#define ll long long
#define int long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define dbg {exit(0);}
#define dbge(x) {cerr<<#x<<'='<<x;exit(0);}
#define dbgn(x) {cerr<<#x<<'='<<x<<endl;}
#define sp cout<<' ';
#define el cout<<'\n';
#define ls u*2
#define rs u*2+1
#define um unordered_map
#define ins insert
#define ass assert
#define sz(a) (int)a.size()
#define mem(a) memset(a,0,sizeof a);
#define inf 1e18
#define foru(a,b,c) for(int a=b;a<=c;a++)
#define ford(a,b,c) for(int a=b;a>=c;a--)
#define HLY "hly_goes_to_thu"
using namespace std;

const int N=500005;
//const int inf=1e17;

template<class T>bool Min(T &x,T y){return x>=y?x=y,0:1;}
template<class T>bool Max(T &x,T y){return x<=y?x=y,0:1;}

int n,q,a[N],b[N];
int ans[N];




struct __{


	struct ___{
		bool b0,b1,b10,b01,b11,b00,p0,p1,p10,p01,a110,a101,a001,a010,tag;
		int l;
	}w[N*4];

	void flip(int u){//还要标记是否进行了全局翻转
		___& x=w[u];
		x.tag^=1;
		swap(x.p0,x.p1);
		swap(x.p10,x.p01);
		swap(x.b0,x.b1);
		swap(x.b10,x.b01);
		swap(x.b11,x.b00);
		swap(x.a110,x.a001);
		swap(x.a101,x.a010);
	}

	void pu(int u,int L,int R){
		___& nw=w[u];
		___& x=w[ls];
		___& y=w[rs];
		nw.l=x.l+y.l;
		nw.p1=x.p1;
		nw.b1=y.b1;
		nw.p0=x.p0;
		nw.b0=y.b0;
		nw.p10=x.p10;
		nw.p01=x.p01;
		nw.b10=y.b10;
		nw.b01=y.b01;
		nw.b11=y.b11;
		nw.b00=y.b00;
		nw.a110=(x.a110|y.a110);
		nw.a101=(x.a101|y.a101);
		nw.a001=(x.a001|y.a001);
		nw.a010=(x.a010|y.a010);

		if(nw.l==2)
			nw.p10|=(x.b1&y.p0),
			nw.b10|=(x.b1&y.p0),
			nw.p01|=(x.b0&y.p1),
			nw.b01|=(x.b0&y.p1),
			nw.b11|=(x.b1&y.p1),
			nw.b00|=(x.b0&y.p0);
		nw.a110|=((x.b1&y.p10)|(x.b11&y.p0));
		nw.a101|=((x.b1&y.p01)|(x.b10&y.p1));
		nw.a001|=((x.b0&y.p01)|(x.b00&y.p1));
		nw.a010|=((x.b0&y.p10)|(x.b01&y.p0));
		return ;
	}


	void pd(int u,int L,int R){
		___& x=w[u];
		if(x.tag==1){
			flip(ls);
			flip(rs);
			x.tag=0;
		}
	}

	int search(int u,int L,int R){
		___& nw=w[u];
		if(nw.a110==0)
			return -1;//最后显然不可能到1啊  不恰好卡到咋办啊  如果当前直接暴力找吧  复杂度不大啊

		___& x=w[ls];
		___& y=w[rs];
		int mid=(L+R)/2;
		pd(u,L,R);
		if(x.a110==1)
			return search(ls,L,mid);
		if(x.b11==1&&y.p0==1)
			return mid-1;
		if(x.b1==1&&y.p10==1)
			return mid;
		if(y.a110==1)
			return search(rs,mid+1,R);
		return -1;
	}

	int sol(){
		int x=search(1,1,n);
		if(x==-1)
			return w[1].a101;
		return n-(x+2)+1;
	}



//	bool back[6];//0 1 10 01 11 00
//	bool pre[5];//0 1 10 01
//	bool a[5];//110 101 001 010



	void build(int u,int L,int R){
		___& x=w[u];
		x.b00=x.b11=x.b10=x.b01=0;
		x.p10=x.p01=0;
		x.a110=x.a101=x.a001=x.a010=0;
		x.p1=(a[L]==1);
		x.b1=(a[R]==1);
		x.p0=(a[L]==0);
		x.b0=(a[R]==0);
		x.tag=0;
		x.l=0;
		if(L==R){
			x.l=1;
            return ;
		}
		int mid=(L+R)/2;
		build(ls,L,mid);
		build(rs,mid+1,R);
		pu(u,L,R);
	}

	void modify(int u,int L,int R,int l,int r){
		if(l<=L&&R<=r){
			flip(u);
			return ;
		}
		if(L>r||R<l)
			return;
		pd(u,L,R);
		int mid=(L+R)/2;
//		if(l<=mid)
			modify(ls,L,mid,l,r);
//		if(mid+1<=r)
			modify(rs,mid+1,R,l,r);
		pu(u,L,R);
	}


}seg;



void solve(){

	cin>>n>>q;
	foru(i,1,n){
		char c;
		cin>>c;
		a[i]=c-'0';
	}


	seg.build(1,1,n);

	ans[0]=seg.sol();
	foru(_,1,q){
		int l,r;
		cin>>l>>r;
		seg.modify(1,1,n,l,r);
		ans[_]=seg.sol();

	}

	int res=0;
	foru(_,0,q){
		res=res^((_+1)*(ans[_]));
	}
	cout<<res<<'\n';












}


signed main(){
//------------------------------------------------------------------------------
//	freopen("a.in","r",stdin);
//	freopen("s.out","w",stdout);
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//------------------------------------------------------------------------------
	int _,__;
	cin>>__>>_;
//	_=1;
	foru(__,1,_)
		solve();




	return 0;


}