给定一个长度为 $n$ 的括号串 $S$ , 有 $m$ 次询问 , 每次询问区间 $[l,r]$ 中的最长子序列长度，满足是合法括号串。

括号串为只由 $($ 和 $)$ 组成的字符串。

合法括号串的定义如下：

1. 空串是合法括号串
2. 如果 $S$ 是合法括号串 , 那么 $(S)$ 是合法括号串
3. 如果 $S$ , $T$ 是合法括号串 , 那么 $ST$ 是合法括号串

输入格式

第一行两个整数 $n,m$ , 含义如题面所示。$(1 \leq n , m \leq 10^5)$

第二行一个字符串 $S$ , 保证 $S$ 中只包含 $($ 和 $)$。

接下来 $m$ 行 , 每行两个整数 $l,r$ , 含义如题面所示。$(1 \leq l \leq r \leq n)$

输出格式

输出共 $m$ 行 , 第 $i$ 行表示第 $i$ 次询问的答案。

样例输入

10 5
))()()()))
6 10
7 8
7 7
7 8
4 9

样例输出

2
2
0
2
4