#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mid ((l+r)/2)
#define eb emplace_back
const int N=1e5+5,M=1e6+5,C=45,MOD=998244353;
int n,m,nw,ans[M];char a[N];
int dpl1[N][C],dpr1[N][C],dpl2[N][C],dpr2[N][C],dpl3[N][C],dpr3[N][C];
struct Query {int op,l,r,x,id;};vector<Query> q;
void W(int &x,int y) {x+=y;if(x>=MOD) x-=MOD;}
void W(int &x,ll y) {x=(x+y)%MOD;}
int W1(int x,int y) {x+=y;return x<MOD?x:x-MOD;}
void slv(int l,int r,vector<Query> q)
{
	if(l==r) return;vector<Query> q1,q2,q3;
	for(auto i:q) if(i.r<=mid) q1.eb(i);else if(i.l>mid) q2.eb(i);else q3.eb(i);
	fill(dpl1[mid+1],dpl1[mid+1]+41,0);fill(dpl2[mid+1],dpl2[mid+1]+41,0);
	fill(dpl3[mid+1],dpl3[mid+1]+41,0);
	for(int i=mid;i>=l;--i)
	{
		for(int j=1;j<=40;++j)
			dpl1[i][j]=W1(dpl1[i+1][j],dpl1[i+1][j-1]),
			dpl2[i][j]=W1(dpl2[i+1][j],dpl2[i+1][j-1]),
			dpl3[i][j]=W1(dpl3[i+1][j],dpl3[i+1][j-1]);
		if(a[i]==')') W(dpl1[i][1],1),W(dpl2[i][1],mid-i+1);else W(dpl3[i][1],1);
	}
	fill(dpr1[mid],dpr1[mid]+41,0);fill(dpr2[mid],dpr2[mid]+41,0);
	fill(dpr3[mid],dpr3[mid]+41,0);
	for(int i=mid+1;i<=r;++i)
	{
		for(int j=1;j<=40;++j)
			dpr1[i][j]=W1(dpr1[i-1][j],dpr1[i-1][j-1]),
			dpr2[i][j]=W1(dpr2[i-1][j],dpr2[i-1][j-1]),
			dpr3[i][j]=W1(dpr3[i-1][j],dpr3[i-1][j-1]);
		if(a[i]=='(') W(dpr1[i][1],1),W(dpr2[i][1],i-mid);else W(dpr3[i][1],1);
	}
	for(auto [op,l1,r1,x,id]:q3) if(op==1)
	{
		W(ans[id],dpl1[l1][x*2]);W(ans[id],dpr1[r1][x*2]);
		for(int i=1;i<x*2;++i)
			W(ans[id],i&1?1ll*dpl3[l1][i]*dpr3[r1][x*2-i]:1ll*dpl1[l1][i]*dpr1[r1][x*2-i]);
	}
	for(int i=mid;i>=l;--i) for(int j=0;j<=40;++j)
		W(dpl1[i][j],dpl1[i+1][j]),W(dpl2[i][j],dpl2[i+1][j]),W(dpl3[i][j],dpl3[i+1][j]);
	for(int i=mid+1;i<=r;++i) for(int j=0;j<=40;++j)
		W(dpr1[i][j],dpr1[i-1][j]),W(dpr2[i][j],dpr2[i-1][j]),W(dpr3[i][j],dpr3[i-1][j]);
	for(auto [op,l1,r1,x,id]:q3) if(op==2)
	{
		W(ans[id],dpl2[l1][x*2]+1ll*dpl1[l1][x*2]*(r1-mid));
		W(ans[id],dpr2[r1][x*2]+1ll*dpr1[r1][x*2]*(mid-l1+1));
		for(int i=1;i<x*2;++i)
			W(ans[id],i&1?1ll*dpl3[l1][i]*dpr3[r1][x*2-i]:1ll*dpl1[l1][i]*dpr1[r1][x*2-i]);
	}
	slv(l,mid,q1);slv(mid+1,r,q2);
}
int main()
{
	scanf("%d %d %s",&n,&m,a+1);q.resize(m);
	for(auto &[op,l,r,x,id]:q) scanf("%d %d %d %d",&op,&l,&r,&x),id=nw++;
	slv(1,n,q);for(int i=0;i<m;++i) printf("%d\n",ans[i]);return 0;
}