A string S whose characters ar one amongst the subsequent 5: (, ), +, − and ?, is alleged to be a sound string if one amongst the subsequent conditions holds:
S= ?
S=(x+y), wherever x and y ar valid strings.
S=(x−y), wherever x and y ar valid strings.
For example, strings ?, (?−?), (?+(?−?)) ar valid strings, whereas strings (?−+), ??, (?), ?−?, (?+?)) aren't.
The power of a sound string S is outlined to be the most price possible by substitution every ? in it by either zero or one and evaluating the ensuing expression.
For example, the ability of (?−?) is one as a result of we are able to obtain (1−0) that evaluates to one.
You are given a sound string S, and letter queries on that. every question is pictured by 2 integers L and R (L≤R). Your task is to seek out the ability of the substring FTO,SL+1,…,SR. it's secured that this substring may be a valid string.
Note: The input of this drawback is giant, therefore use quick input/output ways.
Input Format
The first line of input contains AN number T, denoting the amount of check cases. the outline of T check cases follows:
The first line of every legal action contains the string S.
The next line contains AN number letter, representing the amount of queries to answer.
Each of the subsequent letter lines contains 2 space-separated integers, L and R, representing the question.
Output Format
For each legal action, print one line containing letter space-separated integers, the i-th of that represents the solution to the i-th question.
Constraints
1≤T≤1000
1≤|S|≤106
1≤Q≤106
1≤L≤R≤|S|
∑|S| and ∑Q over all check cases doesn't exceed 106.
Subtasks
Subtask #1 (20 points):
1≤|S|≤1000
1≤Q≤1000
∑|S| and ∑Q over all legal action doesn't exceed 104.
Subtask #2 (80 points):
Original constraints
Sample Input one
3
(?+?)
2
2 2
1 5
(?-(?-?))
2
1 9
4 8
(?-(?+?))
1
1 9
Sample Output one
1 2
2 1
1
Explanation
Test case 1:
Query one: Power of the string ? is 1, because it are often born-again to one.
Query two: Power of the string (?+?) is 2, because it are often born-again to (1+1).
Test case 2:
Query 1: Power of the string (?−(?−?)) is two, because it are often born-again to (1−(0−1)).
Query 2: Power of the string (?−?) is one, because it are often born-again to (1−0).
Test case 3:
Query one: Power of the string (?−(?+?)) is 1, because it are often born-again to (1−(0+0)).
Code: click
ConversionConversion EmoticonEmoticon