いくつかの () が連結された形式で表されるとき、その数列は「良い」数列であるという。 形式的には、長さ $2n$ の数列 $s$ が $s_1 = s_3 = \dots = s_{2n-1} = ($ かつ $s_2 = s_4 = \dots = s_{2n} = )$ を満たすとき、その数列は「良い」数列である。このとき、$n$ をその深さと呼ぶ。

長さ $n$ の ( と ) からなる数列 $s$ が与えられる。$s_l, s_{l+1}, \dots, s_r$ によって形成される数列 $t$ において、深さ $k$ の「良い」部分列の個数を $f(l, r, k)$ とする。

$q$ 個のクエリが与えられる。各クエリは 4 つの数値 $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 で割った余りを出力せよ。

入力

1 行目に 2 つの数値 $n, q$ ($1 \le n \le 10^5, 1 \le q \le 10^6$) が与えられる。 2 行目に長さ $n$ の数列 $s$ が与えられる。 続く $q$ 行に、4 つの数値 $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