//#pragma GCC optimize("Ofast","inline","-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#define MOD 998244353 
using namespace __gnu_pbds;
using namespace std;

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

inline void add1(int &x,int y)
{
	x+=y;
	if(x>=MOD) x-=MOD;
}

inline void add2(int &x,int y)
{
	x+=y;
	if(x<0) x+=MOD;
}

int n,q,c[100010],op[1000010],l_[1000010],r_[1000010],k[1000010];
vector<int> v[400010],g[400010];
int dat[100010][41][2],sum[100010][41][2],ans[1000010],f[400010][21][4];

inline void build(int o,int l,int r)
{
	if(l==r) return;
	int mid=(l+r)/2;
	build(o*2,l,mid);
	build(o*2+1,mid+1,r);
	for(int i=l;i<=r;i++){
		for(int j=0;j<=40;j++) dat[i][j][0]=dat[i][j][1]=0;
	}
	for(int i=mid;i>=l;i--){
		if(i==mid){
			dat[i][0][0]=1;dat[i][0][1]=1;
			if(c[i]==0) dat[i][1][0]=1;
			else dat[i][1][1]=1;
		}
		else{
			for(int j=0;j<=40;j++){
				add1(dat[i][j][0],dat[i+1][j][0]);
				if(j>0&&((c[j]==0&&j%2==1)||(c[j]==1&&j%2==0))) add1(dat[i][j][0],dat[i+1][j-1][0]);
				add1(dat[i][j][1],dat[i+1][j][1]);
				if(j>0&&((c[j]==0&&j%2==0)||(c[j]==1&&j%2==1))) add1(dat[i][j][1],dat[i+1][j-1][1]);
			}
		}
	}
	for(int i=mid;i>=l;i--){
		for(int j=1;j<=40;j++){
			if(i==mid){
				sum[i][j][0]=0;
				if(j==1&&c[i]==0) add1(sum[i][j][0],i);
				sum[i][j][1]=0;
				if(j==1&&c[i]==1) add1(sum[i][j][1],i);
			}
			else{
				sum[i][j][0]=sum[i+1][j][0];
				if((c[i]==0&&j%2==1)||(c[i]==1&&j%2==0)) add1(sum[i][j][0],1ll*dat[i+1][j-1][0]*i%MOD);
				sum[i][j][1]=sum[i+1][j][1];
				if((c[i]==0&&j%2==0)||(c[i]==1&&j%2==1)) add1(sum[i][j][1],1ll*dat[i+1][j-1][1]*i%MOD);
			}
		}
	}
	for(int i=mid+1;i<=r;i++){
			if(i==mid+1){
				dat[i][0][0]=1;dat[i][0][1]=1;
				if(c[i]==0) dat[i][1][0]=1;
				else dat[i][1][1]=1;
			}
			else{
				for(int j=0;j<=40;j++){
					add1(dat[i][j][0],dat[i-1][j][0]);
					if(j>0&&((c[j]==0&&j%2==1)||(c[j]==1&&j%2==0))) add1(dat[i][j][0],dat[i-1][j-1][0]);
					add1(dat[i][j][1],dat[i-1][j][1]);
					if(j>0&&((c[j]==0&&j%2==1)||(c[j]==1&&j%2==0))) add1(dat[i][j][1],dat[i-1][j-1][1]);
				}
			}
	}
	for(int i=mid+1;i<=r;i++){
		for(int j=1;j<=40;j++){
			if(i==mid+1){
				sum[i][j][0]=0;
				if(j==1&&c[i]==0) add1(sum[i][j][0],n-i+1);
				sum[i][j][1]=0;
				if(j==1&&c[i]==1) add1(sum[i][j][1],n-i+1);
			}
			else{
				sum[i][j][0]=sum[i-1][j][0];
				if((c[i]==0&&j%2==1)||(c[i]==1&&j%2==0)) add1(sum[i][j][0],1ll*dat[i-1][j-1][0]*(n-i+1)%MOD);
				sum[i][j][1]=sum[i-1][j][1];
				if((c[i]==0&&j%2==0)||(c[i]==1&&j%2==1)) add1(sum[i][j][1],1ll*dat[i-1][j-1][1]*(n-i+1)%MOD);
			}
		}
	}
	for(int i=0;i<(int)v[o].size();i++){
		int id=v[o][i],o_=op[id],L=l_[id],R=r_[id],K=k[id];
		int ll=L-1,rr=n-R;
		L=max(L,l);R=min(R,r);
		if(o_==1){
			for(int j=1;j<2*K;j++){
				if(j%2==1) add1(ans[id],1ll*dat[L][j][0]*dat[R][2*K-j][1]%MOD);
				else add1(ans[id],1ll*dat[L][j][1]*dat[R][2*K-j][0]%MOD);
			}
		}
		else{
			for(int j=1;j<2*K;j++){
				if(j%2==1){
					add1(ans[id],1ll*dat[L][j][0]*dat[R][2*K-j][1]%MOD*ll%MOD*rr%MOD);
					add2(ans[id],-1ll*dat[L][j][0]*sum[R][2*K-j][1]%MOD*ll%MOD);
					add2(ans[id],-1ll*sum[L][j][0]*dat[R][2*K-j][1]%MOD*rr%MOD);
					add1(ans[id],1ll*sum[L][j][0]*sum[R][2*K-j][1]%MOD);
				}
				else{
					add1(ans[id],1ll*dat[L][j][1]*dat[R][2*K-j][0]%MOD*ll%MOD*rr%MOD);
					add2(ans[id],-1ll*dat[L][j][1]*sum[R][2*K-j][0]%MOD*ll%MOD);
					add2(ans[id],-1ll*sum[L][j][1]*dat[R][2*K-j][0]%MOD*rr%MOD);
					add1(ans[id],1ll*sum[L][j][1]*sum[R][2*K-j][0]%MOD);
				}
			}
		}
	}
	for(int i=1;i<=20;i++){
		f[o][i][0]=f[o*2][i][0];add1(f[o][i][0],f[o*2+1][i][0]);
		f[o][i][1]=f[o*2][i][1];add1(f[o][i][1],f[o*2+1][i][1]);
		f[o][i][2]=f[o*2][i][2];add1(f[o][i][2],f[o*2+1][i][2]);
		f[o][i][3]=f[o*2][i][3];add1(f[o][i][3],f[o*2+1][i][3]);
		for(int j=1;j<2*i;j++){
			if(j%2==1){
				add1(f[o][i][0],1ll*dat[l][j][0]*dat[r][2*i-j][1]%MOD);
				add1(f[o][i][1],1ll*dat[l][j][0]*sum[r][2*i-j][1]%MOD);
				add1(f[o][i][2],1ll*sum[l][j][0]*dat[r][2*i-j][1]%MOD);
				add1(f[o][i][3],1ll*sum[l][j][0]*sum[r][2*i-j][1]%MOD);
			}
			else{
				add1(f[o][i][0],1ll*dat[l][j][1]*dat[r][2*i-j][0]%MOD);
				add1(f[o][i][1],1ll*dat[l][j][1]*sum[r][2*i-j][0]%MOD);
				add1(f[o][i][2],1ll*sum[l][j][1]*dat[r][2*i-j][0]%MOD);
				add1(f[o][i][3],1ll*sum[l][j][1]*sum[r][2*i-j][0]%MOD);
			}
		}
	}
	for(int i=0;i<(int)g[o].size();i++){
		int id=g[o][i],o_=op[id],L=l_[id],R=r_[id],K=k[id];
		int ll=L-1,rr=n-R;
		if(o_==1){
			add1(ans[id],1ll*f[o][K][0]);
		}
		else{
			add1(ans[id],1ll*f[o][K][0]*ll%MOD*rr%MOD);
			add2(ans[id],-1ll*f[o][K][1]*ll%MOD);
			add2(ans[id],-1ll*f[o][K][2]*rr%MOD);
			add1(ans[id],f[o][K][3]);
		}
	}
}

inline void query(int o,int l,int r,int x,int y,int id)
{
	int mid=(l+r)/2;
	if(x<=l&&r<=y){
		g[o].push_back(id);
		return;
	}
	if(x<=mid&&mid+1<=y) v[o].push_back(id);
	if(x<=mid) query(o*2,l,mid,x,y,id);
	if(y>=mid+1) query(o*2+1,mid+1,r,x,y,id);
	return;
}

signed main()
{
	ios::sync_with_stdio(false);cin.tie(0);
	mt19937 Rand(998244353);
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		char ch;cin>>ch;
		if(ch=='(') c[i]=0;
		else c[i]=1;
	}
	for(int i=1;i<=q;i++){cin>>op[i]>>l_[i]>>r_[i]>>k[i];
		query(1,1,n,l_[i],r_[i],i);
	}
	cerr<<clock()<<endl;
	build(1,1,n);
	for(int i=1;i<=q;i++) cout<<ans[i]<<'\n';
	return 0;
}