/*
T4:
Ä£Ä⣺
³õʼÔÚx 
ÈôxΪ1£¬¾ÍÒ»Ö±ÍùÇ°×ßµ½x=0»òÕß½áÊø£¬È»ºó×ßÒ»²½ans++
ÈôxΪ0£¬ÕÒµ½ÓұߵÚÒ»¸ö=1µÄλÖÃy£¬ans+=2*(y-x)+1,x--,°ÑyµÄλÖÃÉèΪ0
½áÊøÌõ¼þ£º1ɾÍêÁË 

ÔÙ¼ÓÉÏÓÐÒ»¸ö±©Á¦ÊÇ´¿´¿µÄÄ£Ä⣬¿ÉÒÔµÃ45·Ö

 
*/
#include <bits/stdc++.h>

using namespace std;

const int MAXN=1e6+50,P=998244353;

int N,Q;
char s[MAXN];
int a[MAXN],b[MAXN];

long long Solve() 
{
	long long ans=0;
	int x=0,y=0;
	for(int i=1;i<=N;i++)
	{
		x+=a[i];
		b[i]=a[i];
	}
	if(x==0)
	return 0;
	y=x;
	while(a[y]!=1)
	y++;
	int Cnt=0;
	for(int i=1;i<=N;i++)
	{
		Cnt+=a[i];
	}
	while(x)
	{
		while(x&&b[x]==1)
		{
			ans++;
			b[x]=0;
			x--;
			Cnt--;
		}
		if(Cnt==0||x==0)
		break;
		while(y<=N&&b[y]==0)
		y++;
	//	cout<<"Now:"<<x<<" "<<y<<endl;
		ans+=2ll*(y-x)+1;
		x--;
		y++;
		Cnt--;
		if(Cnt==0)
		break;
		while(a[y]!=1)
		y++;
	}
	return ans;
}

void Solve1()
{
	while(Q--)
	{
		int l,r;
		scanf("%d%d",&l,&r);
		for(int i=l;i<=r;i++)
		{
			a[i]^=1;
		}
		printf("%lld\n",Solve());
	}
}
void Solve2()
{
	while(Q--)
	{
		int l,r;
		scanf("%d%d",&l,&r);
		for(int i=l;i<=r;i++)
		{
			a[i]^=1;
		}
		int Cnt=0;
		for(int i=1;i<=N;i++)
		{
			Cnt+=a[i];
			b[i]=a[i];
		}
		long long ans=0;
		while(Cnt)
		{
			if(b[Cnt]==0)
			{
				b[Cnt]=1;
				Cnt++;
			}
			else
			{
				b[Cnt]=0;
				Cnt--;
			}
			ans++;
		}
		printf("%lld\n",ans);
	}
}

int main()
{
//	freopen("zero.in","r",stdin);
//	freopen("zero.out","w",stdout);
	scanf("%d%d%s",&N,&Q,&s[1]);
	for(int i=1;i<=N;i++)
	{
		a[i]=(s[i]=='1');
	}
	/*
	if(N<=20&&Q<=20)
	{
		
	}
	*/
	if((N<=2000&&Q<=2000)||(Q<=20))
	{
		Solve1();
		return 0;
	}
	Solve2();
//	return 0;
}