这题思路简单，但实现复杂。

注意我的时间复杂度是 $O(n\log^2n)$ 的，但明显跑不满，还是次优解。

考虑先把表达式树建出来，把“是否取反”直接挂在节点上。然后直接维护哪些区间答案是 True。与其它题解不同的在于我写的平衡树（FHQ-treap）。

平衡树里维护一堆数字，注意数量是偶数，然后从小到大排序后 $a_1,a_2,a_3,\dots,a_{2n}$ 表示 $[a_1,a_2),\dots,[a_{2n-1},a_{2n})$ 这些地方是有值的（注意区间左闭右开，这样取反异或时才好维护）。问题变为判断 $\le x$ 的点是否有奇数个。

$\texttt{[x]}$ 初始化时直接插入 $x$ 和 $10^9+1$。

对于合并，考虑启发式合并（所以是 $O(n\log^2n)$ 的）。

如果插入的地方有数了相当于抵消了，改为删除，以下我就统称“插入”了。

1. 异或操作。注意到直接把元素数量少的那边的元素全部插入进大的一边就行了。
2. 或操作。相当于把小的区间全都合并进去。对于每一个区间，把中间的数全都清空（缩成一段了），然后如果端点不在区间内就单独插入，来保证形成的区间没问题。
3. 与操作。相当于把大区间不在小区间内的全都去掉。对于每一个区间间的间隙，把中间的数全都清空，然后如果端点原本在一个区间中，那么要加入新的端点位置，来保证形成的区间没问题。
4. 如果这个区间要取反，就相当于异或上 $[1,10^9+1)$。

关于“来保证形成的区间没问题”，用图片来描述就长这样：

注意可能需要判小的区间为空时的情况（或和异或操作不管，与操作全部清空）

代码：（也是终于会写平衡树了）

#include<bits/stdc++.h>
using namespace std;
namespace estidi{
	const int mn=1000003;
	random_device R;
	mt19937 G(R());
	unsigned long long rand(){
		return uniform_int_distribution<unsigned long long>(0,-1ULL)(G);
	}
	struct t_node{
		int val,size,ls,rs;
		unsigned long long p;
	}t[mn*40];
	struct node{
		int type,rev,ls,rs;
	}a[mn];
	int ncnt,cnt,root[mn];
	vector<int>tmp;
	stack<int>nd,op;
	void pushup(int x){
		if(!x)
			return;
		t[x].size=t[t[x].ls].size+t[t[x].rs].size+1;
	}
	void split(int x,int &l,int &r,int v){
		if(!x){
			l=0;
			r=0;
			return;
		}
		if(t[x].val<=v){
			l=x;
			split(t[x].rs,t[l].rs,r,v);
		}
		else{
			r=x;
			split(t[x].ls,l,t[r].ls,v);
		}
		pushup(x);
	}
	void merge(int &x,int l,int r){
		if(!l||!r){
			x=l|r;
			pushup(x);
			return;
		}
		if(t[l].p>t[r].p){
			x=l;
			merge(t[x].rs,t[l].rs,r);
		}
		else{
			x=r;
			merge(t[x].ls,l,t[r].ls);
		}
		pushup(x);
	}
	void add(int x,int &root){
		int r1,r2,r3,r4;
		split(root,r1,r2,x);
		split(r1,r3,r4,x-1);
		if(!r4){
			t[++cnt]={x,1,0,0,rand()};
			r4=cnt;
			assert(cnt<=mn*40000000LL);
		}
		else
			r4=0;
		merge(r1,r3,r4);
		merge(root,r1,r2);
	}
	void getlist(int x){
		if(!x)
			return;
		getlist(t[x].ls);
		tmp.push_back(t[x].val);
		getlist(t[x].rs);
	}
	void mergeseg(int l,int r,int &root){
//		cerr<<"m"<<l<<" "<<r<<" "<<root<<endl;
		int r1,r2,r3,r4;
		split(root,r1,r2,l-1);
		split(r2,r3,r4,r-1);
		if(t[r1].size%2==0)
			add(l,r1);
		if(t[r4].size%2==0)
			add(r,r4);
		merge(root,r1,r4);
	}
	void cutseg(int l,int r,int &root){
//		cerr<<"c"<<l<<" "<<r<<" "<<root<<endl;
		int r1,r2,r3,r4;
		split(root,r1,r2,l-1);
		split(r2,r3,r4,r-1);
		if(t[r1].size%2==1)
			add(l,r1);
		if(t[r4].size%2==1)
			add(r,r4);
		merge(root,r1,r4);
	}
	void get(int x){
		if(a[x].type<0){
			get(a[x].ls);
			get(a[x].rs);
			if(t[root[a[x].ls]].size<t[root[a[x].rs]].size)
				swap(a[x].ls,a[x].rs);
			root[x]=root[a[x].ls];
			tmp.clear();
			getlist(root[a[x].rs]);
			if(tmp.size()){
				if(a[x].type==-2)
					for(int i=0;i<tmp.size();i++)
						add(tmp[i],root[x]);
				if(a[x].type==-3)
					for(int i=0;i<tmp.size();i+=2)
						mergeseg(tmp[i],tmp[i+1],root[x]);
				if(a[x].type==-1){
					cutseg(1,tmp[0],root[x]);
					for(int i=1;i+1<tmp.size();i+=2)
						cutseg(tmp[i],tmp[i+1],root[x]);
					cutseg(tmp[tmp.size()-1],1000000001,root[x]);
				}
			}
			else
				if(a[x].type==-1)
					cutseg(1,1000000001,root[x]);
		}
		else{
			add(a[x].type,root[x]);
			add(1000000001,root[x]);
		}
		if(a[x].rev){
			add(1,root[x]);
			add(1000000001,root[x]);
		}
		assert(t[root[x]].size%2==0);
//		cerr<<x<<" ";
//		assert(a[x].type);
//		if(a[x].type>0)
//			cerr<<"["<<a[x].type<<"]";
//		else{
//			if(a[x].type==-1)
//				cerr<<"&";
//			if(a[x].type==-2)
//				cerr<<"^";
//			if(a[x].type==-3)
//				cerr<<"|";
//		}
//		cerr<<" "<<a[x].rev<<endl;
//		tmp.clear();
//		getlist(root[x]);
//		for(int i=0;i<tmp.size();i++)
//			cerr<<tmp[i]<<" ";
//		cerr<<endl;
	}
	int main(){
		int n,q,v;
		string s;
		scanf("%d%d",&n,&q);
		cin>>s;
		for(int i=0;i<s.size();i++){
			if(s[i]=='(')
				op.push(-999);
			if(s[i]=='!')
				op.push(0);
			if(s[i]=='&'){
				while(op.size()&&op.top()>-1){
					if(op.top()==0)
						a[nd.top()].rev^=1;
					else{
						int x,y;
						x=nd.top();
						nd.pop();
						y=nd.top();
						nd.pop();
						a[++ncnt]={op.top(),0,x,y};
						nd.push(ncnt);
					}
					op.pop();
				}
				op.push(-1);
			}
			if(s[i]=='^'){
				while(op.size()&&op.top()>-2){
					if(op.top()==0)
						a[nd.top()].rev^=1;
					else{
						int x,y;
						x=nd.top();
						nd.pop();
						y=nd.top();
						nd.pop();
						a[++ncnt]={op.top(),0,x,y};
						nd.push(ncnt);
					}
					op.pop();
				}
				op.push(-2);
			}
			if(s[i]=='|'){
				while(op.size()&&op.top()>-3){
					if(op.top()==0)
						a[nd.top()].rev^=1;
					else{
						int x,y;
						x=nd.top();
						nd.pop();
						y=nd.top();
						nd.pop();
						a[++ncnt]={op.top(),0,x,y};
						nd.push(ncnt);
					}
					op.pop();
				}
				op.push(-3);
			}
			if(s[i]==')'){
				while(op.top()!=-999){
					if(op.top()==0)
						a[nd.top()].rev^=1;
					else{
						int x,y;
						x=nd.top();
						nd.pop();
						y=nd.top();
						nd.pop();
						a[++ncnt]={op.top(),0,x,y};
						nd.push(ncnt);
					}
					op.pop();
				}
				op.pop();
			}
			if(s[i]=='['){
				i++;
				int num=0;
				while(s[i]!=']'){
					num=num*10+s[i]-'0';
					i++;
				}
				a[++ncnt]={num,0,0,0};
				nd.push(ncnt);
			}
		}
		while(op.size()){
			if(op.top()==0)
				a[nd.top()].rev^=1;
			else{
				int x,y;
				x=nd.top();
				nd.pop();
				y=nd.top();
				nd.pop();
				a[++ncnt]={op.top(),0,x,y};
				nd.push(ncnt);
			}
			op.pop();
		}
		assert(nd.size()==1);
		get(nd.top());
		while(q--){
			scanf("%d",&v);
			int r1,r2;
			split(root[nd.top()],r1,r2,v);
			if(t[r1].size%2==1)
				printf("True\n");
			else
				printf("False\n");
			merge(root[nd.top()],r1,r2);
		}
		return 0;
	}
}
int main(){
	estidi::main();
	return 0;
}