CF380C.Sereja and Brackets

Sereja has a bracket sequence _s_1, _s_2, ..., s__n, or, in other words, a string s of length n, consisting of characters "(" and ")".

Sereja needs to answer m queries, each of them is described by two integers l__i, r__i (1 ≤ l__i ≤ r__i ≤ n). The answer to the i-th query is the length of the maximum correct bracket subsequence of sequence s__l__i, s__l__i + 1, ..., s__r__i. Help Sereja answer all queries.

You can find the definitions for a subsequence and a correct bracket sequence in the notes.

Sereja 有一个括号序列 $s_1, s_2, \dots, s_n$，换句话说，是一个长度为 $n$ 的字符串 $s$，由字符 '(' 和 ')' 组成。

Sereja 需要回答 $m$ 个查询，每个查询由两个整数 $l_i, r_i$（满足 $1 \le l_i \le r_i \le n$）描述。第 $i$ 个查询的答案是子序列 $s_{l_i}, s_{l_i+1}, \dots, s_{r_i}$ 中最长的合法括号子序列的长度。请帮助 Sereja 回答所有查询。

关于“子序列”和“合法括号序列”的定义，请参见题目末尾的注释。

The first line contains a sequence of characters _s_1, _s_2, ..., s__n (1 ≤ n ≤ 106) without any spaces. Each character is either a "(" or a ")". The second line contains integer m (1 ≤ m ≤ 105) — the number of queries. Each of the next m lines contains a pair of integers. The i-th line contains integers l__i, r__i (1 ≤ l__i ≤ r__i ≤ n) — the description of the i-th query.

第一行包含一个长度为 $n$（$1 \leq n \leq 10^6$）的字符串 $s_1, s_2, \dots, s_n$，中间无空格。每个字符为 ( 或 )。
第二行包含一个整数 $m$（$1 \leq m \leq 10^5$），表示查询次数。
接下来的 $m$ 行中，每行包含一对整数。第 $i$ 行包含整数 $l_i, r_i$（$1 \leq l_i \leq r_i \leq n$），表示第 $i$ 个查询的区间。

Print the answer to each question on a single line. Print the answers in the order they go in the input.

每个问题的答案单独占一行输出。按输入中问题的顺序输出答案。

A subsequence of length |x| of string s = _s_1_s_2... s|s| (where |s| is the length of string s) is string x = _s__k_1_s__k_2... s__k|x| (1 ≤ _k_1 < _k_2 < ... < k|x| ≤ |s|).

A correct bracket sequence is a bracket sequence that can be transformed into a correct aryphmetic expression by inserting characters "1" and "+" between the characters of the string. For example, bracket sequences "()()", "(())" are correct (the resulting expressions "(1)+(1)", "((1+1)+1)"), and ")(" and "(" are not.

For the third query required sequence will be «()».

For the fourth query required sequence will be «()(())(())».

字符串 $s = s_1s_2\ldots s_{|s|}$（其中 $|s|$ 表示字符串 $s$ 的长度）的一个长度为 $|x|$ 的子序列是指形如 $x = s_{k_1}s_{k_2}\ldots s_{k_{|x|}}$ 的字符串（满足 $1 \le k_1 < k_2 < \cdots < k_{|x|} \le |s|$）。

合法括号序列（correct bracket sequence）是指：通过在该括号序列的字符之间插入若干个字符 "1" 和 "+"，可将其转化为一个合法的算术表达式。例如，括号序列 "()()"、"(())" 是合法的（对应表达式分别为 "(1)+(1)"、"((1+1)+1)"），而 ")(" 和 "(" 则不合法。

对于第三个查询，所要求的序列为 «()»。

对于第四个查询，所要求的序列为 «()(())(())»。