D. Bracket Sequence
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

A sequence is good when it can be represented by several $$$\mathtt{()}$$$ connected together.

Formally, a sequence $$$s$$$ of length $$$2n$$$ is good when $$$s_1=s_3=\dots=s_{2n-1}=\mathtt{(}$$$ and $$$s_2=s_4=\dots=s_{2n}=\mathtt{)}$$$. In that case, we call $$$n$$$ its $$$\bf{depth}$$$.

Given a sequence $$$s$$$ of length $$$n$$$ which consists of $$$\mathtt{(}$$$ and $$$\mathtt{)}$$$. Let $$$f(l,r,k)$$$ be the number of good subsequences with depth $$$k$$$ in the sequence $$$t$$$ formed by $$$s_l,s_{l+1},\dots,s_r$$$.

You are given $$$q$$$ queries, each query contains four numbers $$$op,l,r,k$$$.

  • If $$$op=1$$$, you need to calculate $$$f(l,r,k)$$$.
  • If $$$op=2$$$, you need to calculate $$$\sum_{l\leq l'\leq r'\leq r}f(l',r',k)$$$.

Since the answer could be huge, you need to output the answer modulo $$$998244353$$$.

Input

The first line contains two numbers $$$n$$$, $$$q$$$ ($$$1\leq n\leq 10^5$$$, $$$1\leq q\leq10^6$$$).

The second line contains the sequence $$$s$$$ of length $$$n$$$.

The following $$$q$$$ lines contain four numbers $$$op,l,r,k$$$ ($$$op \in \{1,2\}$$$, $$$1\leq l\leq r\leq n$$$, $$$1\leq k\leq20$$$).

Output

Output $$$q$$$ integers: the answer to each query, modulo $$$998244353$$$.

Example
Input
5 20
(()()
1 1 2 1
1 1 3 1
1 1 4 1
1 1 5 1
1 2 3 1
1 2 4 1
1 2 5 1
1 3 4 1
1 3 5 1
1 4 5 1
2 1 3 1
2 1 4 1
2 1 5 1
2 2 3 1
2 2 4 1
2 2 5 1
2 3 5 1
2 4 5 1
1 1 5 2
2 1 5 2
Output
0
2
2
5
1
1
3
0
1
1
3
6
16
1
2
7
2
1
2
3