// Lynkcat.
// Problem: F. Frustration and Bracket Sequences
// Contest: Codeforces - Day 1: JAGain in Petrozavodsk (Select Virtual participation)
// URL: https://muscat2023a.contest.codeforces.com/group/haunPN6WKE/contest/431432/problem/F
// Memory Limit: 1024 MB
// Time Limit: 4000 ms

#include<bits/stdc++.h>
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define inf 1e9
#define mod 998244353
#define int ll
#define N 150005
using namespace std;
const int B=400;
int n,m,a[N];
int From[N];
int rev[N];
int tag[N];
int K[2*B+7];
int val[(N+B-1)/B+7][B*2+7][2];
int sm[(N+B-1)/B][2];
int tot[N][2][2];
inline int calc(int r)
{
	if (r%2==0) return (1+r/2)*(r/2);
	return (1+r/2)*(r/2)+(r+1)/2;
}
inline void pushdown(int x)
{
	if (!tag[x]) return;
	for (int i=(x-1)*B+1;i<=min(n,x*B);i++)
		a[i]^=1;
	tag[x]=0;
}
inline void rebuild(int x)
{
	rev[x]=0;
	int o;
	
	o=0;
	memset(K,0,sizeof(K));
	for (int i=B+B+2;i>=0;i--) val[x][i][0]=0;
	for (int i=(x-1)*B+1;i<=min(n,x*B);i++)
	{
		if (a[i]==0)
		{
			o++;
		} else o--;
		int u=-o;
		u+=B+2;
		// cout<<"?"<<i<<" "<<u<<'\n';
		if (u>=1)
		{
			val[x][u-1][0]+=u+1;
			K[u-1]++;
		}
		if (u>=2)
		{
			val[x][u-2][0]+=u;
			K[u-2]++;
		}
	}
	for (int i=B+B+2;i>=0;i--)
	{
		val[x][i][0]+=val[x][i+2][0];
		K[i]+=K[i+2];
	}
	for (int i=B+B+2;i>=0;i--)
	{
		val[x][i][0]-=K[i]*i;
		// cout<<x<<" "<<a[x]<<" "<<i<<" "<<val[x][i][0]<<'\n';
	}
	sm[x][0]=o;
	tot[x][1][0]=K[1];
	tot[x][0][0]=K[0];
	
	o=0;
	memset(K,0,sizeof(K));
	for (int i=B+B+2;i>=0;i--) val[x][i][1]=0;
	for (int i=(x-1)*B+1;i<=min(n,x*B);i++)
	{
		if (a[i]==1)
		{
			o++;
		} else o--;
		int u=-o;
		u+=B+2;
		// cout<<"?"<<i<<" "<<u<<'\n';
		if (u>=1)
		{
			val[x][u-1][1]+=u+1;
			K[u-1]++;
		}
		if (u>=2)
		{
			val[x][u-2][1]+=u;
			K[u-2]++;
		}
	}
	sm[x][1]=o;
	for (int i=B+B+2;i>=0;i--)
	{
		val[x][i][1]+=val[x][i+2][1];
		K[i]+=K[i+2];
	}
	for (int i=B+B+2;i>=0;i--)
		val[x][i][1]-=K[i]*i;
	tot[x][1][1]=K[1];
	tot[x][0][1]=K[0];
}	
mt19937_64 rnd(19382723);
void BellaKira()
{
	cin>>n>>m;
	for (int i=1;i<=n;i++)
	{
		char ch;
		cin>>ch;
		
		// if (rnd()%2) ch='(';
		// else ch=')';
		
		if (ch=='(')
		{
			a[i]=0;
		} else a[i]=1;
	}
	for (int i=1;i<=n;i++) From[i]=(i-1)/B+1;
	for (int i=1;i<=From[n];i++)
		rebuild(i);
	while (m--)
	{
		int opt,l,r;
		cin>>opt>>l>>r;
		
		// opt=rnd()%2+1,l=rnd()%n+1,r=rnd()%n+1;
		// if (l>r) swap(l,r);
		
		if (opt==1)
		{
			if (From[l]==From[r])
			{
				pushdown(From[l]);
				for (int j=l;j<=r;j++) a[j]^=1;
				rebuild(From[l]);
			} else
			{
				pushdown(From[l]);
				for (int j=l;j<=From[l]*B;j++) a[j]^=1;
				rebuild(From[l]);
				pushdown(From[r]);
				for (int j=(From[r]-1)*B+1
				;j<=r;j++) a[j]^=1;
				rebuild(From[r]);
				for (int j=From[l]+1;j<From[r];j++)
				{
					rev[j]^=1;
					tag[j]^=1;
				}
			}
		} else
		{
			pushdown(From[l]);
			pushdown(From[r]);
			int ans=0;
			int pre=0;
			if (From[l]==From[r])
			{
				pushdown(From[l]);
				for (int j=l;j<=r;j++)
				{
					if (a[j]==0) pre++;
					else pre--;
					if (pre<0) ans+=(-pre+1)/2;
				}
				if (pre>0)
				{
					ans=pre;
					ans+=calc(pre);
					pre=-pre;
					for (int j=l;j<=r;j++)
					{
						if (a[j]==0) pre++;
						else pre--;
						if (pre<0) ans+=(-pre+1)/2;
					}
				} else
				{
					ans+=calc(-pre-1);
					ans+=-pre;
				}
				cout<<ans<<'\n';
			} else
			{
				pushdown(From[l]);
				pushdown(From[r]);
				
				int pre=0;
				for (int j=l;j<=From[l]*B;j++)
				{
					if (a[j]==0) pre++;
					else pre--;
				}
				// cout<<"?"<<pre<<" "<<a[l]<<'\n';
				for (int j=From[l]+1;j<From[r];j++)
				{
					pre+=sm[j][rev[j]];
					// cout<<j<<" "<<sm[j][0]<<" "<<sm[j][1]<<" "<<rev[j]<<'\n';
				}
				// cout<<"?"<<pre<<'\n';
				for (int j=(From[r]-1)*B+1;j<=r;j++)
				{
					if (a[j]==0) pre++;
					else pre--;
				}
				// cout<<"?"<<pre<<'\n';
				if (pre>0)
				{
					ans+=pre;
					ans+=calc(pre);
					pre=-pre;
				} else 
				{
					ans+=-pre;
					ans+=calc(-pre-1);
					pre=0;
				}
				// cout<<"?"<<pre<<'\n';
				for (int j=l;j<=From[l]*B;j++)
				{
					if (a[j]==0) pre++;
					else pre--;
					if (pre<0) ans+=(-pre+1)/2;
				}
				// cout<<"?"<<pre<<" "<<ans<<" "<<a[1]<<'\n';
				for (int j=From[l]+1;j<From[r];j++)
				{
					if (pre>=B)
					{
						pre+=sm[j][rev[j]];
						continue;
					}
					int lst=ans;
					if (pre+B+2<0)
					{
						ans+=
						(val[j][((pre+B+2)%2!=0)][rev[j]]+
						(-pre-B-2+((pre+B+2)%2!=0))
						*tot[j][((pre+B+2)%2!=0)][rev[j]])/2;
						
					}else
						ans+=val[j][pre+B+2][rev[j]]/2;
					pre+=sm[j][rev[j]];
					continue;
				}
				for (int j=(From[r]-1)*B+1;j<=r;j++)
				{
					if (a[j]==0) pre++;
					else pre--;
					if (pre<0) ans+=(-pre+1)/2;
				}
				cout<<ans<<'\n';
			}
		}
	}
		
}
signed main()
{
	IOS;
	cin.tie(0);
	int T=1;
	while (T--)
	{
		BellaKira();
	}
}