求卡常

#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;
int T,n,m,a[N],b[N],f[2][N],g[2][N];
struct node{
	int fx,fn,fp,gx[3],gn[3],gp;
	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;
	}
	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();}
	void init(int x=1,int l=1,int r=5e4+2){
		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];
	}
	node opt(int l,int r,int v_=0){return L=l,R=r,v=v_,opt_();}
	node opt_(int x=1,int l=1,int r=5e4+2){
		if(l>R||L>r||L>R)return{-N,N,0,{-N,-N,-N},{N,N,N},0};
		if(L<=l&&r<=R)return d[x]+=v,a[x]*=v;
		node s=opt_(lx,l,mid)+opt_(rx,mid+1,r);
		a[x]=a[lx]+a[rx];
		return a[x]*=d[x],s*=d[x];
	}
}h[2];
int chk(int k){
	int t=k&1;
	node p=h[t].opt(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].opt((p+1)/2,(n+1)/2,v);
	h[1].opt(p/2,n/2,v);
}
int qry(){
	int l=1,r=n-1,ans=n;
	while(l<=r){
		if(!chk(mid))l=mid+1;
		else ans=mid,r=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;
	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(){
	// freopen("defense6.in","r",stdin);
	// freopen("defense6.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>T>>T;
	while(T--)slv();
	cerr<<clock()<<"ms";
	return 0;
}