#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,mod=998244353,K=40;
struct node{
	int op,l,r,k,id;
};
int n,Q,k,f[N][K+2][2],g[N][K+2][2],p[N],ans[N*10];
char str[N];
void Clr(vector<node> &q)
{
	vector<node> v;
	swap(v,q);
}
void pls(int &a,int b)
{
	if((a+=b)>=mod) a-=mod;
}
void clr(int l,int r)
{
	for(int i=l;i<=r;i++)
		for(int j=0;j<=K;j++)
			for(int k=0;k<2;k++)
				f[i][j][k]=g[i][j][k]=0;
}
void solve(int l,int r,vector<node> q)
{
	if(l==r||q.empty()) return;
	int mid=(l+r)>>1;
	vector<node> q1,q2,q3;
	for(auto k:q) if(k.r<=mid) q1.push_back(k);
	else if(k.l>mid) q2.push_back(k);
	else q3.push_back(k);
	Clr(q);
	solve(l,mid,q1),solve(mid+1,r,q2);
	for(int i=0;i<2;i++)
		f[mid+1][0][i]=g[mid][0][i]=1;
	for(int i=mid;i>=l;i--)
		for(int j=0;j<=K;j++)
		{
			pls(f[i][j+1][p[i]],f[i+1][j][p[i]^1]);
			pls(f[i][j][0],f[i+1][j][0]);
			pls(f[i][j][1],f[i+1][j][1]);
		}
	for(int i=mid+1;i<=r;i++)
		for(int j=0;j<=K;j++)
		{
			pls(g[i][j+1][p[i]],g[i-1][j][p[i]^1]);
			pls(g[i][j][0],g[i-1][j][0]);
			pls(g[i][j][1],g[i-1][j][1]);
		}
	for(auto k:q3)
		if(k.op==1)
		{
			int m=2*k.k;
			for(int j=0;j<=m;j++)
				pls(ans[k.id],1ll*f[k.l][j][0]*g[k.r][m-j][1]%mod);
		}
	for(int i=mid;i>=l;i--)
		for(int j=0;j<=K;j++)
			for(int p=0;p<2;p++)
				pls(f[i][j][p],f[i+1][j][p]);
	for(int i=mid+1;i<=r;i++)
		for(int j=0;j<=K;j++)
			for(int p=0;p<2;p++)
				pls(g[i][j][p],g[i-1][j][p]);
	for(auto k:q3)
		if(k.op==2)
		{
			int m=2*k.k;
			for(int j=0;j<=m;j++)
				pls(ans[k.id],1ll*f[k.l][j][0]*g[k.r][m-j][1]%mod);
		}
	clr(l,r);
	for(int i=l;i<=mid+1;i++)
		for(int j=0;j<2;j++) f[i][0][j]=1;
	for(int i=mid;i<r;i++)
		for(int j=0;j<2;j++) g[i][0][j]=1;
	for(int i=mid;i>=l;i--)
		for(int j=0;j<=K;j++)
		{
			pls(f[i][j+1][p[i]],f[i+1][j][p[i]^1]);
			pls(f[i][j][0],f[i+1][j][0]);
			pls(f[i][j][1],f[i+1][j][1]);
		}
	for(int i=mid+1;i<=r;i++)
		for(int j=0;j<=K;j++)
		{
			pls(g[i][j+1][p[i]],g[i-1][j][p[i]^1]);
			pls(g[i][j][0],g[i-1][j][0]);
			pls(g[i][j][1],g[i-1][j][1]);
		}
	for(int i=mid;i>=l;i--)
		for(int j=0;j<=K;j++)
			for(int p=0;p<2;p++)
				pls(f[i][j][p],f[i+1][j][p]);
	for(int i=mid+1;i<=r;i++)
		for(int j=0;j<=K;j++)
			for(int p=0;p<2;p++)
				pls(g[i][j][p],g[i-1][j][p]);
	for(auto k:q3)
		if(k.op==2)
		{
			int m=2*k.k,w=k.id;
			pls(ans[w],f[k.l][m][1]);
			pls(ans[w],f[k.r][m][1]);
		}
	clr(l,r);
}
int main()
{
	scanf("%d%d%s",&n,&Q,str+1);
	for(int i=1;i<=n;i++) p[i]=(str[i]==')');
	vector<node> q(Q);
	for(int i=0;i<Q;i++)
		scanf("%d%d%d%d",&q[i].op,&q[i].l,&q[i].r,&q[i].k),q[i].id=i;
	solve(1,n,q);
	for(int i=0;i<Q;i++) printf("%d\n",ans[i]);
}