#P18173. Bracket Sequence

Bracket Sequence

Bracket Sequence

称一个括号序列是好的,当且仅当它由若干个 () 依次拼接而成。形式化地,长度为 2k2k 的序列满足:奇数位置均为 (,偶数位置均为 )。称这样的序列深度为 kk。

例如 ()、()()、()()() 都是好的;(()) 不是好的。这里的“深度”指 () 的个数,并不是通常括号序列的嵌套深度。

给定长度为 nn 的括号字符串 ss,下标从 1 开始。定义 f(l,r,k)f(l,r,k) 为子串 s[l..r]s[l..r] 中,深度为 kk 的好子序列数量。

子序列可以不连续,但必须保留原顺序;选择的下标集合不同就视为不同子序列,即使得到的括号字符串相同。

需要回答 qq 个询问,每个询问给出 op,l,r,kop,l,r,k:

  • 若 op=1op=1,输出 f(l,r,k)f(l,r,k);
  • 若 op=2op=2,输出
∑l≤a≤b≤rf(a,b,k).\sum_{l\le a\le b\le r} f(a,b,k).

所有答案对 998244353998244353 取模。字符串不会修改。

输入格式

第一行两个整数 n,qn,q,满足 1≤n≤1051\le n\le10^5、1≤q≤1061\le q\le10^6。

第二行一个长度为 nn 的字符串 ss,仅由 ( 和 ) 组成。

接下来 qq 行,每行四个整数 op,l,r,kop,l,r,k,满足

$$op\in\{1,2\},\qquad1\le l\le r\le n,\qquad1\le k\le20.$$

输出格式

对每个询问输出一行一个整数,表示对应答案模 998244353998244353 的结果。

样例

输入:

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