题目描述

如果一个序列可以由若干个 () 连接而成，则称该序列是好的。 形式化地，一个长度为 $2n$ 的序列 $s$ 是好的，当且仅当 $s_1 = s_3 = \dots = s_{2n-1} = ($ 且 $s_2 = s_4 = \dots = s_{2n} = )$。在这种情况下，我们称 $n$ 为其深度。

给定一个由 ( 和 ) 组成的长度为 $n$ 的序列 $s$。令 $f(l, r, k)$ 表示在由 $s_l, s_{l+1}, \dots, s_r$ 构成的序列 $t$ 中，深度为 $k$ 的好子序列的数量。

你需要处理 $q$ 次询问，每次询问包含四个数字 $op, l, r, k$。

• 若 $op = 1$，你需要计算 $f(l, r, k)$。
• 若 $op = 2$，你需要计算 $\sum_{l \le l' \le r' \le r} f(l', r', k)$。

由于答案可能非常大，你需要输出答案对 $998244353$ 取模的结果。

输入格式

第一行包含两个数字 $n, q$ ($1 \le n \le 10^5, 1 \le q \le 10^6$)。 第二行包含长度为 $n$ 的序列 $s$。 接下来的 $q$ 行，每行包含四个数字 $op, l, r, k$ ($op \in \{1, 2\}, 1 \le l \le r \le n, 1 \le k \le 20$)。

输出格式

输出 $q$ 个整数，即每次询问的答案，对 $998244353$ 取模。

样例

输入格式 1

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

输出格式 1

0
2
2
5
1
1
3
0
1
1
3
6
16
1
2
7
2
1
2
3