A sequence is good when it can be represented by several () connected together. Formally, a sequence $s$ of length $2n$ is good when $s_1 = s_3 = \dots = s_{2n-1} = ($ and $s_2 = s_4 = \dots = s_{2n} = )$. In that case, we call $n$ its depth.

Given a sequence $s$ of length $n$ which consists of ( and ). 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 \le l' \le r' \le 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 \le n \le 10^5, 1 \le q \le 10^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 \le l \le r \le n, 1 \le k \le 20$).

Output

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

Examples

Input 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

Output 1

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