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$$$.
Since the answer could be huge, you need to output the answer modulo $$$998244353$$$.
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 $$$q$$$ integers: the answer to each query, modulo $$$998244353$$$.
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
0 2 2 5 1 1 3 0 1 1 3 6 16 1 2 7 2 1 2 3
