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 «()(())(())».

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = "import sys\n\ninput = sys.stdin.readline\n\ns = input()\n\nM = int(input())\n\n\ndef next_pow_2(n):\n    p = 1\n    while p < n:\n        p <<= 1\n    return p\n\n\ndef represented_range(node, size):\n    l = node\n    r = node\n    while l < size:\n        l = 2 * l\n        r = 2 * r + 1\n    return l - size, r - size\n\n\nclass SegTree:\n    def __init__(self, size):\n        self.size = next_pow_2(size)\n        self.answer = [0] * (2 * self.size)\n        self.opened = [0] * (2 * self.size)\n        self.closed = [0] * (2 * self.size)\n\n    # O(size * (O(func) + O(init))\n    def build(self, s):\n        for i in range(self.size):\n            self.answer[self.size + i] = 0\n            self.opened[self.size + i] = 1 if i < len(s) and s[i] == '(' else 0\n            self.closed[self.size + i] = 1 if i < len(s) and s[i] == ')' else 0\n\n        for i in range(self.size - 1, 0, -1):\n            matched = min(self.opened[2 * i], self.closed[2 * i + 1])\n            self.answer[i] = self.answer[2 * i] + self.answer[2 * i + 1] + matched\n            self.opened[i] = self.opened[2 * i] + self.opened[2 * i + 1] - matched\n            self.closed[i] = self.closed[2 * i] + self.closed[2 * i + 1] - matched\n\n    # O(log(size)), [l,r]\n    def query(self, l, r):\n        l += self.size\n        r += self.size\n\n        eventsL = []\n        eventsR = []\n        while l <= r:\n            if l & 1:\n                eventsL.append((self.answer[l], self.opened[l], self.closed[l]))\n                l += 1\n            if not (r & 1):\n                eventsR.append((self.answer[r], self.opened[r], self.closed[r]))\n                r -= 1\n            l >>= 1\n            r >>= 1\n\n        answer = 0\n        opened = 0\n        for a, o, c in eventsL + eventsR[::-1]:\n            matched = min(c, opened)\n            answer += a + matched\n            opened += o - matched\n\n        return answer\n\n\nseg = SegTree(len(s))\nseg.build(s)\n\nfor i in range(M):\n    l, r = [int(_) for _ in input().split()]\n    print(2 * seg.query(l - 1, r - 1))"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13219