panda-and-query

One day while playing with parentheses '{' and '}' , Panda came across an interesting question , given a string A consisting of parentheses we've to perform the following operation: Given two integers L and R,find the length of correct parentheses subsequence.

Note: All the indices (L and R) for above operation are according to 1 indexed.  

INPUT: 
First line of input contains a string comprising of parentheses '{'and '}'.
Second line contains T the number of queries. 
Next T lines contains two space separated integers L and R.

OUTPUT:
For each query print length of correct parentheses subsequence in new line. 

Constraints
1 ≤ |Length of the string| ≤ 10^5
1 ≤ T ≤ 10^5  
1 ≤ L ≤ R ≤ 10^5    

SAMPLE INPUT
{{}}{
5
1 2
1 4
2 3
1 5
2 4

SAMPLE OUTPUT
0
4
2
4
2

Explanation

For Query 1: correct Bracket subseqence length is 0 {{.  
For Query 5: correct Bracket subseqence length is 2 {}}.

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions: