Codeforces Round #223 (Div. 2) E. 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

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

题意：给你一个括号序列，q个询问，求区间内括号匹配的数量；

思路：线段数区间合并；

　　　一个线段树存三个数，l,m,r;

　　　l表示区间内除去以匹配的左括号的数量；

　　　r表示区间内除去以匹配的右括号的数量；

　　　m表示匹配好的左右括号的数量；

　　　对于左边的区间，和右边的区间，只要将左边的l和右边的尽量匹配即可；

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<queue>
#include<algorithm>
#include<stack>
#include<cstring>
#include<vector>
#include<list>
#include<set>
#include<map>
using namespace std;
#define ll long long
#define pi (4*atan(1.0))
#define eps 1e-14
#define bug(x)  cout<<"bug"<<x<<endl;
const int N=1e6+2,M=1e7+10,inf=1e9+10;
const ll INF=1e18+10,mod=1e9+7;

///   数组大小
char s[N];

struct ans
{
    int x,y,z;
    ans(){}
    ans(int xx,int yy,int zz)
    {
        x=xx;y=yy;z=zz;
    }
};

struct SGT
{
    int LT[N<<2],RT[N<<2],MT[N<<2];
    void pushup(int pos)
    {
        int k=min(LT[pos<<1],RT[pos<<1|1]);
        MT[pos]=MT[pos<<1]+MT[pos<<1|1]+2*k;
        LT[pos]=LT[pos<<1]+LT[pos<<1|1]-k;
        RT[pos]=RT[pos<<1]+RT[pos<<1|1]-k;
    }
    void build(int l,int r,int pos)
    {
        if(l==r)
        {
            LT[pos]=0;
            RT[pos]=0;
            MT[pos]=0;
            if(s[l]=='(')
                LT[pos]++;
            else
                RT[pos]++;
            return;
        }
        int mid=(l+r)>>1;
        build(l,mid,pos<<1);
        build(mid+1,r,pos<<1|1);
        pushup(pos);
    }
    ans query(int L,int R,int l,int r,int pos)
    {
        if(L==l&&r==R)
            return ans(LT[pos],MT[pos],RT[pos]);
        int mid=(l+r)>>1;
        if(R<=mid)
            return query(L,R,l,mid,pos<<1);
        else if(L>mid)
            return query(L,R,mid+1,r,pos<<1|1);
        else
        {
            ans a=query(L,mid,l,mid,pos<<1);
            ans b=query(mid+1,R,mid+1,r,pos<<1|1);
            int k=min(a.x,b.z);
            int m=a.y+b.y+2*k;
            int l=a.x+b.x-k;
            int r=a.z+b.z-k;
            return ans(l,m,r);
        }
    }
};
SGT tree;
int main()
{
    scanf("%s",s+1);
    int x=strlen(s+1);
    tree.build(1,x,1);
    int q;
    scanf("%d",&q);
    while(q--)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        printf("%d
",tree.query(l,r,1,x,1).y);
    }
    return 0;
}
/*
))(()))))())())))))())((()()))))()))))))))))))
9
26 42
21 22
6 22
7 26
43 46
25 27
32 39
22 40
2 45
*/