求卡常

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pii pair<int,int>
#define ve vector<int>
#define fi first
#define se second
#define pb push_back
#define mid ((l+r)>>1)
#define lx (x<<1)
#define rx (x<<1|1)
#define pcnt __builtin_popcount
using namespace std;
const int N=(1<<18)+2,M=5e4+2;
int C,T,n,m,ans,a[N],b[N],f[2][N],g[2][N];
struct node{
	int fx,fn,fp,gx[3],gn[3],gp;
	inline node&operator*=(int v){
		if(!v)return*this;
		fx+=v,fn+=v;
		for(int t=0;t<3;t++)gx[t]-=v,gn[t]-=v;
		return*this;
	}
	inline node operator+(const node&x){
		node y;
		y.fx=max(fx,x.fx);
		y.fn=min(fn,x.fn);
		y.fp=min(min(fp,x.fp),x.fn-fx);
		y.gp=min(gp,x.gp);
		for(int t=0;t<3;t++){
			y.gx[t]=max(gx[t],x.gx[t]),
			y.gn[t]=min(gn[t],x.gn[t]);
			for(int r=0;r<3;r++)
				y.gp=min(y.gp,x.gn[t]-gx[r]+(t>r));
		}
		return y;
	}
};
struct sgt{
	node a[N];int d[N];
	int*ff,*gg,L,R,v;
	void init(int*f0,int*g0){ff=f0,gg=g0,init(1,1,M);}
	void init(int x,int l,int r){
		d[x]=0;
		if(l==r)
			return a[x]={ff[l],ff[l],0,{-N,-N,-N},{N,N,N},0},
				a[x].gx[l%3]=a[x].gn[l%3]=gg[l],void();
		init(lx,l,mid),init(rx,mid+1,r);
		a[x]=a[lx]+a[rx];
	}
	void mdf(int l,int r,int v_){L=l,R=r,v=v_,mdf_(1,1,M);}
	void mdf_(int x,int l,int r){
		return(L<=l&&r<=R?(d[x]+=v,a[x]*=v):(L<=mid&&(mdf_(lx,l,mid),0),R>mid&&(mdf_(rx,mid+1,r),0),(a[x]=a[lx]+a[rx])*=d[x])),void();
	}
	node qry(int l,int r){return L=l,R=r,qry_(1,1,M);}
	node qry_(int x,int l,int r){
		return L<=l&&r<=R?a[x]:(R<=mid?(qry_(lx,l,mid)*=d[x]):(L>mid?(qry_(rx,mid+1,r)*=d[x]):((qry_(lx,l,mid)+qry_(rx,mid+1,r))*=d[x])));
	}
}h[2];
int chk(int k){
	int t=k&1;
	node p=h[t].qry(k/2+1,(n+!t)/2);
	if(p.fn<-k/2||p.fp<-k||p.gp<-k)return 0;
	for(int z=0;z<3;z++)
		if(p.gn[z]+(z+k%3+(t?4:2))/3<-k/3)return 0;
	return 1;
}
void mdf(int p,int v){
	h[0].mdf((p+1)/2,(n+1)/2,v);
	n>1&&(h[1].mdf(max(p/2,1),n/2,v),0);
}
int qry(){
	int l,r;
	if(ans){
		l=max(ans-4,1),r=min(ans+3,n-1),ans=n;
		while(l<=r)chk(mid)?(ans=mid,r=mid-1):(l=mid+1);
		if(ans<n)return ans;
	}
	l=1,r=n-1,ans=n;
	while(l<=r)chk(mid)?(ans=mid,r=mid-1):(l=mid+1);
	return ans;
}
void init(){
	for(int i=1;i<=n;i++)
		b[i]=b[i-1]+a[i],
		f[i&1][i/2]=b[i]-i/2;
	if(n&1)f[0][n/2+1]=b[n]-n/2-1;
	else f[1][n/2]=b[n]-n/2;
	for(int t=0;t<2;t++)
		for(int i=1;i<=(n+!t)/2;i++)
			g[t][i]=i/3-f[t][i]-(i+i==n+!t);
	h[0].init(f[0],g[0]);
	h[1].init(f[1],g[1]);
}
void slv(){
	string s;
	cin>>n>>m>>s,s=" "+s,ans=0;
	for(int i=1;i<=n;i++)a[i]=(s[i]=='0');
	init();
	cout<<qry()<<(m?" ":"");
	for(int x;m--;)
		cin>>x,mdf(x,(a[x]^=1)?1:-1),
		cout<<qry()<<(m?" ":"");
	cout<<'\n';
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>C>>T;
	while(T--)slv();
	return 0;
}