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.


-----Input-----

The first line contains a sequence of characters s_1, s_2, ..., s_{n} (1 ≤ n ≤ 10^6) without any spaces. Each character is either a "(" or a ")". The second line contains integer m (1 ≤ m ≤ 10^5) — 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.


-----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 = s_1s_2... s_{|}s| (where |s| is the length of string s) is string x = s_{k}_1s_{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 «()(())(())».

Difficulty: competition

Starter code:

Solutions:
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))


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

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

        answer = 0
        opened = 0
        for a, o, c in eventsL + eventsR[::-1]:
            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))


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

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

        answer = 0
        opened = 0
        for a, o, c in eventsL + eventsR[::-1]:
            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))