380_C. Sereja and Brackets
Sereja has a bracket sequence s1, s2, ..., sn, 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 li, ri (1 ≤ li ≤ ri ≤ n). The answer to the i-th query is the length of the maximum correct bracket subsequence of sequence sli, sli + 1, ..., sri. Help Sereja answer all queries.

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

Input

The first line contains a sequence of characters s1, s2, ..., sn (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 li, ri (1 ≤ li ≤ ri ≤ n) — the description of the i-th query.

Output

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

Examples

Input

())(())(())(
7
1 1
2 3
1 2
1 12
8 12
5 11
2 10


Output

0
0
2
10
4
6
6

Note

A subsequence of length |x| of string s = s1s2... s|s| (where |s| is the length of string s) is string x = sk1sk2... sk|x| (1 ≤ k1 < k2 < ... < 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 «()(())(())».
```python
import sys
input = sys.stdin.readline

s = input()

M = int(input())


def next_pow_2(n):
    p = 1
    while p < n:
        p <<= 1
    return p


def represented_range(node, size):
    l = node
    r = node
    while l < size:
        l = 2*l
        r = 2*r + 1
    return l-size, r-size


class SegTree:
    def __init__(self, size):
        self.size = next_pow_2(size)
        self.answer = [0] * (2*self.size)
        self.opened = [0] * (2*self.size)
        self.closed = [0] * (2*self.size)

    # O(size * (O(func) + O(init))
    def build(self, s):
        for i in range(self.size):
            self.answer[self.size + i] = 0
            self.opened[self.size + i] = 1 if i < len(s) and s[i] == '(' else 0
            self.closed[self.size + i] = 1 if i < len(s) and s[i] == ')' else 0

        for i in range(self.size - 1, 0, -1):
            matched = min(self.opened[2*i], self.closed[2*i+1])
            self.answer[i] = self.answer[2*i] + self.answer[2*i+1] + matched
            self.opened[i] = self.opened[2*i] + self.opened[2*i+1] - matched
            self.closed[i] = self.closed[2*i] + self.closed[2*i+1] - matched

    # O(log(size)), [l,r]
    def query(self, l, r):
        l += self.size
        r += self.size

        eventsR = []
        answer = 0
        opened = 0
        while l <= r:
            if l & 1:
                matched = min(self.closed[l], opened)
                answer += self.answer[l] + matched
                opened += self.opened[l] - matched
                l += 1
            if not (r & 1):
                eventsR.append((self.answer[r], self.opened[r], self.closed[r]))
                r -= 1
            l >>= 1
            r >>= 1

        for i in range(len(eventsR)-1, -1, -1):
            a, o, c = eventsR[i]
            matched = min(c, opened)
            answer += a + matched
            opened += o - matched

        return answer


seg = SegTree(len(s))
seg.build(s)

for i in range(M):
    l, r = [int(_) for _ in input().split()]
    print(2*seg.query(l-1, r-1))

```