class Binary_Indexed_Tree(): def __init__(self, L, calc, unit, inv, index=1): """ calc を演算とする N 項の Binary Indexed Tree を作成 calc: 演算 (2変数関数, 可換群) unit: 群 calc の単位元 (x+e=e+x=xを満たすe) inv : 群 calc の逆元 (1変数関数, x+y(x)=y(x)+x=e をみたす y(x)) """ self.calc=calc self.unit=unit self.inv=inv self.index=index N=len(L) d=max(1,(N-1).bit_length()) k=2**d X=[None]+[unit]*k self.num=k self.depth=d if L: for i in range(len(L)): p=i+1 while p<=k: X[p]=self.calc(X[p],L[i]) p+=p&(-p) self.data=X def index_number(self, k, index=1): """ 第 k 要素の値を出力する. k : 数列の要素 index: 先頭の要素の番号 """ return self.sum(k,k,index) def add(self, k, x, index=1): """ 第 k 要素に x を加え, 更新を行う. k : 数列の要素 x : 加える値 index: 先頭の要素の番号 """ p=k+(1-index) while p<=self.num: self.data[p]=self.calc(self.data[p],x) p+=p&(-p) def update(self, k, x, index=1): """ 第 k 要素を x に変え, 更新を行う. k: 数列の要素 x: 更新後の値 """ a=self.index_number(k,index) y=self.calc(self.inv(a),x) self.add(k,y,index) def sum(self, From, To, index=1): """ 第 From 要素から第 To 要素までの総和を求める. ※From!=1を使うならば, 群でなくてはならない. From : 始まり To : 終わり index: 先頭の要素の番号 """ alpha=max(1,From+(1-index)) beta=min(self.num,To+(1-index)) if alpha>beta: return self.unit elif alpha==1: return self.__section(beta) else: return self.calc(self.inv(self.__section(alpha-1)),self.__section(beta)) def __section(self,x): """ B[1]+...+B[x] を求める. """ S=self.unit while x>0: S=self.calc(self.data[x],S) x-=x&(-x) return S def all_sum(self): return self.data[-1] def binary_search(self, cond, index=1): """ cond(B[1]+...+B[k]) を満たす最小の k を返す. cond: 単調増加 ※ cond(unit)=True の場合の返り値は index-1 ※ cond(B[1]+...+B[k]) なる k が存在しない場合の返り値は self.num+index """ if cond(self.unit): return index-1 j=0 r=self.num t=r data=self.data alpha=self.unit for _ in range(self.depth+1): if j+t<=self.num: beta=self.calc(alpha,data[j+t]) if not cond(beta): alpha=beta j+=t t>>=1 return j+index def __getitem__(self,index): if isinstance(index,int): return self.index_number(index,self.index) else: return [self.index_number(t,self.index) for t in index] def __setitem__(self,index,val): self.update(index,val,self.index) #================================================== from operator import add,neg import sys input=sys.stdin.readline write=sys.stdout.write N,Q=map(int,input().split()) S=["*"]+list(input()) B=Binary_Indexed_Tree([0]*(N-1),add,0,neg,1) for i in range(1,N): if S[i]=="(" and S[i+1]==")": B.add(i,1,1) Ans=[] for _ in range(Q): type,*A=map(int,input().split()) if type==1: i,=A if S[i]==")": S[i]="(" else: S[i]=")" if i>=1: if S[i-1]=="(" and S[i]==")": B.update(i-1,1,1) else: B.update(i-1,0,1) if i