#include<bits/stdc++.h>
using namespace std;
using i64=long long;
constexpr i64 mod=998244353;
int n,m;
char str[100010];
struct Mat{
   array<i64,20>f[2][2];
   i64 g[41];
   void add(const Mat&o,i64 w){
      for(int x:{0,1})for(int y:{0,1})for(int i=0;i<20;i++)
      (f[x][y][i]+=o.f[x][y][i]*w)%=mod;
      for(int i=0;i<=40;i++)(g[i]+=o.g[i]*w)%=mod;
   }
}prod[100010],inv[100010],invi[100010],prodi[100010],s[100010],si[100010];
i64 calc(const Mat&x,const Mat&y,int k){
   i64 res=y.g[k*2];
   for(int i=1;i<=k;i++){
      (res+=x.g[k*2-1]*y.f[0][1][k-i]+x.g[k*2]*y.f[1][1][k-i])%=mod;
   }return res;
}
int main(){
   scanf("%d%d%s",&n,&m,str+1);
   prod[0].f[0][0][0]=prod[0].f[1][1][0]=prodi[0].f[0][0][0]=prodi[0].f[1][1][0]=1;
   prod[0].g[0]=prodi[0].g[0]=1;
   inv[0].f[0][0][0]=inv[0].f[1][1][0]=invi[0].f[0][0][0]=invi[0].f[1][1][0]=1;
   inv[0].g[0]=invi[0].g[0]=1;
   for(int i=1;i<=n;i++){
      prod[i]=prod[i-1],prodi[i]=prodi[i-1];
      inv[i]=inv[i-1],invi[i]=invi[i-1];
      if(str[i]=='('){
         (prod[i].g[1]+=1)%=mod,(prodi[i].g[1]+=i)%=mod;
         for(int k=2;k<=20;k++){
            (prod[i].g[k*2-1]+=prod[i-1].g[(k-1)*2])%=mod;
            (prodi[i].g[k*2-1]+=prodi[i-1].g[(k-1)*2])%=mod;
         }
         for(int o:{0,1}){
            for(int k=0;k<19;k++)
            (prod[i].f[o][0][k+1]+=prod[i-1].f[o][1][k])%=mod,
            (prodi[i].f[o][0][k+1]+=prodi[i-1].f[o][1][k])%=mod;
         }
         for(int k=1;k<=20;k++){
            (inv[i].g[k*2-1]+=mod-inv[i-1].f[0][0][k-1])%=mod;
            (inv[i].g[k*2]+=mod-inv[i-1].f[0][1][k-1])%=mod;
            (inv[i].g[k*2-1]+=(mod-i)*inv[i-1].f[0][0][k-1])%=mod;
            (inv[i].g[k*2]+=(mod-i)*inv[i-1].f[0][1][k-1])%=mod;
         }
         for(int o:{0,1}){
            for(int k=0;k<19;k++)
            (inv[i].f[1][o][k+1]+=mod-inv[i-1].f[0][o][k])%=mod,
            (invi[i].f[1][o][k+1]+=mod-invi[i-1].f[0][o][k])%=mod;
         }
      }else{
         for(int k=2;k<=20;k++){
            (prod[i].g[k*2]+=prod[i-1].g[k*2-1])%=mod;
            (prodi[i].g[k*2]+=prodi[i-1].g[k*2-1])%=mod;
         }
         for(int o:{0,1}){
            for(int k=0;k<19;k++)
            (prod[i].f[o][1][k+1]+=prod[i-1].f[o][0][k])%=mod,
            (prodi[i].f[o][1][k+1]+=prodi[i-1].f[o][0][k])%=mod;
         }
         for(int o:{0,1}){
            for(int k=0;k<19;k++)
            (inv[i].f[0][o][k+1]+=mod-inv[i-1].f[1][o][k])%=mod,
            (invi[i].f[0][o][k+1]+=mod-invi[i-1].f[1][o][k])%=mod;
         }
      }
      s[i]=s[i-1],si[i]=si[i-1];
      s[i].add(prod[i],1),si[i].add(prodi[i],1);
   }
   for(int op,l,r,k;m--;){
      scanf("%d%d%d%d",&op,&l,&r,&k);
      if(op==1){
         Mat tmp=s[r];tmp.add(s[l-1],mod-1);
         printf("%lld\n",calc(inv[l-1],tmp,k));
      }else{
         Mat tmp=si[r];tmp.add(si[l-1],mod-1);
         i64 v=calc(invi[l-1],tmp,k);
         tmp=s[r],tmp.add(s[l-1],k);
         printf("%lld\n",(mod-(l-1))*calc(inv[l-1],tmp,k));
      }
   }
   return 0;
}