Read problem statements in [Bengali], [Russian], [Mandarin] and [Vietnamese] as well.

A string S whose characters are one of the following 5: (, ), +, - and ?, is said to be a *valid string* if one of the following conditions holds:
S = \ ?
S = (x+y), where x and y are valid strings.
S = (x-y), where x and y are valid strings.

For example, strings ?, (?-?), (?+(?-?)) are valid strings, while strings (?-+), ??, (?), ?-?, (?+?)) are not.

The *power* of a valid string S is defined to be the maximum value attainable by replacing each ? in it by either 0 or 1 and evaluating the resulting expression.

For example, the power of (?-?) is 1 because we can obtain (1 - 0) which evaluates to 1.

You are given a valid string S, and Q queries on it. Each query is represented by two integers L and R (L≤ R).
Your task is to find the power of the substring S_{L}, S_{L+1}, \dots, S_{R}. It is guaranteed that this substring is a valid string.

Note: The input of this problem is large, so use fast input/output methods.

------ Input Format ------ 

- The first line of input contains an integer T, denoting the number of test cases. The description of T test cases follows:
- The first line of each test case contains the string S.
- The next line contains an integer Q, representing the number of queries to answer.
- Each of the following Q lines contains two space-separated integers, L and R, representing the query.

------ Output Format ------ 

For each test case, print one line containing Q space-separated integers, the i-th of which represents the answer to the i-th query.

------ Constraints ------ 

$1 ≤ T ≤ 1000$
$1 ≤ |S| ≤ 10^{6}$
$1 ≤ Q ≤ 10^{6}$
$1 ≤ L ≤ R ≤ |S|$
$\sum{|S|}$ and $\sum{Q}$ over all test cases does not exceed $10^{6}$.

------ subtasks ------ 

Subtask #1 (20 points):
$1 ≤ |S| ≤ 1000$
$1 ≤ Q ≤ 1000$
$\sum{|S|}$ and $\sum{Q}$ over all test case does not exceed $10^{4}$.

Subtask #2 (80 points):
Original constraints

----- Sample Input 1 ------ 
3
(?+?)
2
2 2
1 5
(?-(?-?))
2
1 9
4 8
(?-(?+?))
1
1 9
----- Sample Output 1 ------ 
1 2
2 1
1
----- explanation 1 ------ 
Test case 1:
- Query 1: Power of the string $?$ is $1$, as it can be converted to $1$.
- Query 2: Power of the string $(?+?)$ is $2$, as it can be converted to $(1+1)$.

Test case 2:
- Query 1: Power of the string $(?-(?-?))$ is $2$, as it can be converted to $(1-(0-1))$.
- Query 2: Power of the string $(?-?)$ is $1$, as it can be converted to $(1-0)$.

Test case 3:
- Query 1: Power of the string $(?-(?+?))$ is $1$, as it can be converted to $(1-(0+0))$.

Difficulty: VERY_HARD
Tags: String algorithms

Dynamic programming

Data structures

Mathematics
Skill types: Dynamic programming

Data structures

Starter code:

Solutions:
import sys
sys.setrecursionlimit(10 ** 8)
for _ in range(int(input())):
	s = input()
	dic = {}

	def do(ini, se):
		(index, ma, mi, sign) = (ini + 1, 0, 0, True)
		while se[index] != ')':
			char = se[index]
			if char == '?':
				if sign:
					ma += 1
				else:
					mi += 1
			elif char == '+':
				sign = True
			elif char == '-':
				sign = False
			elif char == '(':
				arr = do(index, se)
				if sign:
					ma += arr[0]
					mi += arr[1]
				else:
					ma += arr[1]
					mi += arr[0]
				index = arr[2]
			index = index + 1
		dic[ini] = ma
		return [ma, mi, index]
	do(0, s)
	ques = int(input())
	res = []
	for __ in range(ques):
		(ini, fin) = map(int, input().split())
		if ini == fin:
			res.append(1)
		else:
			res.append(dic[ini - 1])
	print(*res)


import sys
sys.setrecursionlimit(10 ** 8)
total_input = int(input())
for _ in range(total_input):
	s = input()
	dic = {}

	def do(ini, s):
		(idx, maxx, minn, sign) = (ini + 1, 0, 0, True)
		while s[idx] != ')':
			char = s[idx]
			if char == '?':
				if sign:
					maxx += 1
				else:
					minn += 1
			elif char == '+':
				sign = True
			elif char == '-':
				sign = False
			elif char == '(':
				arr = do(idx, s)
				if sign:
					maxx += arr[0]
					minn += arr[1]
				else:
					maxx += arr[1]
					minn += arr[0]
				idx = arr[2]
			idx += 1
		dic[ini] = maxx
		return [maxx, minn, idx]
	do(0, s)
	ques = int(input())
	ans = []
	for __ in range(ques):
		(ini, fin) = map(int, input().split())
		if ini == fin:
			ans.append(1)
		else:
			ans.append(dic[ini - 1])
	print(*ans)


import sys
sys.setrecursionlimit(10 ** 8)
for _ in range(int(input())):
	s = input()
	d = {}

	def solve(i, s):
		(j, max, min, sign) = (i + 1, 0, 0, True)
		while s[j] != ')':
			char = s[j]
			if char == '?':
				if sign:
					max += 1
				else:
					min += 1
			elif char == '-':
				sign = False
			elif char == '+':
				sign = True
			elif char == '(':
				a = solve(j, s)
				if sign:
					max += a[0]
					min += a[1]
				else:
					max += a[1]
					min += a[0]
				j = a[2]
			j += 1
		d[i] = max
		return [max, min, j]
	solve(0, s)
	ans = []
	for _ in range(int(input())):
		(i, f) = map(int, input().split())
		ans.append(1 if i == f else d[i - 1])
	print(*ans)


inf = float('inf')
import sys
import pprint
import logging
from logging import getLogger
import array
import collections
import os

def main():
	osi = '/home/ps/Documents/cp/input.txt'
	oso = '/home/ps/Documents/cp/output.txt'
	if os.path.exists(osi):
		sys.stdin = open(osi, 'r')
		sys.stdout = open(oso, 'w')

def solve():
	for i in range(*maps()):
		s = input()
		q = [list(maps()) for _ in range(*maps())]
		n = len(s)
		dp = [1] * n
		turn = 1
		st = []
		for i in range(n):
			if s[i] == ')':
				dp[i] = dp[st.pop()]
				turn = dp[i]
				continue
			if s[i] == '-':
				turn ^= 1
			if s[i] == '(':
				st.append(i)
			dp[i] = turn
		pre = [[0, 0] for _ in range(n)]
		for i in range(1, n):
			pre[i][0] += pre[i - 1][0]
			pre[i][1] += pre[i - 1][1]
			if s[i] == '?':
				pre[i][dp[i]] += 1
		ans = []
		for (l, r) in q:
			if l == r:
				ans.append(1)
				continue
			ans.append(pre[r - 1][dp[r - 1]] - pre[l - 1][dp[l - 1]])
		print(*ans)
main()

def input():
	return sys.stdin.readline().rstrip('\r\n')

def maps():
	return [int(i) for i in input().split()]
logging.basicConfig(format='%(message)s', level=logging.WARNING)
logger = getLogger(__name__)
logger.setLevel(logging.INFO)

def debug(msg, *args):
	logger.info(f'{msg}={pprint.pformat(args)}')
solve()


inf = float('inf')
import sys
import pprint
import logging
from logging import getLogger
import array
import collections

def solve():
	for _ in range(*maps()):
		s = input()
		n = len(s)
		q = [list(maps()) for _ in range(*maps())]
		dp = [0] * n
		curr = True
		st = []
		for i in range(n):
			if s[i] == ')':
				dp[i] = dp[st.pop()]
				curr = dp[i]
				continue
			dp[i] = curr
			if s[i] == '(':
				st.append(i)
			if s[i] == '-':
				curr ^= True
		pre = [[0, 0] for _ in range(n)]
		for i in range(1, n):
			pre[i][0] += pre[i - 1][0]
			pre[i][1] += pre[i - 1][1]
			if s[i] == '?':
				pre[i][dp[i]] += 1
		ans = []
		for (l, r) in q:
			if l == r:
				ans.append(1)
				continue
			x = pre[r - 1][dp[r - 1]] - pre[l - 1][dp[l - 1]]
			ans.append(x)
		print(*ans)

def input():
	return sys.stdin.readline().rstrip('\r\n')

def maps():
	return [int(i) for i in input().split()]
logging.basicConfig(format='%(message)s', level=logging.WARNING)
logger = getLogger(__name__)
logger.setLevel(logging.INFO)

def debug(msg, *args):
	logger.info(f'{msg}={pprint.pformat(args)}')
solve()


def wildcard(s):
	b = []
	m = []
	o = []
	d = {}
	for i in range(len(s)):
		if s[i] == '(':
			b.append(i + 1)
		elif s[i] == '?':
			m.append([0, 1])
			d[i + 1, i + 1] = 1
		elif s[i] == '-' or s[i] == '+':
			o.append(s[i])
		else:
			if o[-1] == '+':
				d[b[-1], i + 1] = max(m[-1]) + max(m[-2])
				temp = [min(m[-1]) + min(m[-2]), max(m[-1]) + max(m[-2])]
			else:
				d[b[-1], i + 1] = max(m[-2]) - min(m[-1])
				temp = [min(m[-2]) - max(m[-1]), max(m[-2]) - min(m[-1])]
			b.pop()
			m.pop()
			m.pop()
			m.append(temp)
			o.pop()
	return d
for _ in range(int(input())):
	s = input()
	find = wildcard(s)
	new = []
	for _ in range(int(input())):
		(x, y) = map(int, input().split())
		new.append(find[x, y])
	print(*new)


import sys
sys.setrecursionlimit(10 ** 8)

def wildcardreplace(L, s):
	(ind, longg, shor, symb) = (L + 1, 0, 0, True)
	while s[ind] != ')':
		C = s[ind]
		if C == '?':
			if symb:
				longg += 1
			else:
				shor += 1
		elif C == '+':
			symb = True
		elif C == '-':
			symb = False
		elif C == '(':
			a = wildcardreplace(ind, s)
			if symb:
				longg += a[0]
				shor += a[1]
			else:
				longg += a[1]
				shor += a[0]
			ind = a[2]
		ind += 1
	list1[L] = longg
	return [longg, shor, ind]
t = int(input())
for i in range(t):
	s = input()
	list1 = {}
	wildcardreplace(0, s)
	Q = int(input())
	li = []
	for i in range(Q):
		(L, R) = map(int, input().split())
		if L == R:
			li.append(1)
		else:
			li.append(list1[L - 1])
	print(*li)


import sys
sys.setrecursionlimit(10 ** 8)
T = int(input())
for t in range(T):
	s = input()
	dic = dict()

	def do(i, s):
		(idx, maxx, minn, count) = (i + 1, 0, 0, True)
		while s[idx] != ')':
			char = s[idx]
			if char == '?':
				if count:
					maxx += 1
				else:
					minn += 1
			elif char == '+':
				count = True
			elif char == '-':
				count = False
			elif char == '(':
				arr = do(idx, s)
				if count:
					maxx += arr[0]
					minn += arr[1]
				else:
					maxx += arr[1]
					minn += arr[0]
				idx = arr[2]
			idx += 1
		dic[i] = maxx
		return [maxx, minn, idx]
	do(0, s)
	ques = int(input())
	ans = []
	for __ in range(ques):
		(i, fin) = map(int, input().split())
		if i == fin:
			ans.append(1)
		else:
			ans.append(dic[i - 1])
	print(*ans)


import sys
sys.setrecursionlimit(10 ** 8)
t = int(input())
for _ in range(t):
	s = input()
	dic = {}

	def do(ini, s):
		(x, maxx, minn, sign) = (ini + 1, 0, 0, True)
		while s[x] != ')':
			char = s[x]
			if char == '?':
				if sign:
					maxx += 1
				else:
					minn += 1
			elif char == '+':
				sign = True
			elif char == '-':
				sign = False
			elif char == '(':
				arr = do(x, s)
				if sign:
					maxx += arr[0]
					minn += arr[1]
				else:
					maxx += arr[1]
					minn += arr[0]
				x = arr[2]
			x += 1
		dic[ini] = maxx
		return [maxx, minn, x]
	do(0, s)
	q = int(input())
	ans = []
	for _ in range(q):
		(ini, f) = map(int, input().split())
		if ini == f:
			ans.append(1)
		else:
			ans.append(dic[ini - 1])
	print(*ans)


import sys
sys.setrecursionlimit(10 ** 8)
tt = int(input())
for _ in range(tt):
	ttdeststr = input()
	ttde = {}

	def do(ttdest, ttdeststr):
		(op, mvc, mnnc, mncsr) = (ttdest + 1, 0, 0, True)
		while ttdeststr[op] != ')':
			char = ttdeststr[op]
			if char == '?':
				if mncsr:
					mvc += 1
				else:
					mnnc += 1
			elif char == '+':
				mncsr = True
			elif char == '-':
				mncsr = False
			elif char == '(':
				arr = do(op, ttdeststr)
				if mncsr:
					mvc += arr[0]
					mnnc += arr[1]
				else:
					mvc += arr[1]
					mnnc += arr[0]
				op = arr[2]
			op += 1
		ttde[ttdest] = mvc
		return [mvc, mnnc, op]
	do(0, ttdeststr)
	ques = int(input())
	ans = []
	for __ in range(ques):
		(ttdest, fin) = map(int, input().split())
		if ttdest == fin:
			ans.append(1)
		else:
			ans.append(ttde[ttdest - 1])
	print(*ans)


import sys
sys.setrecursionlimit(10 ** 8)
for _ in range(int(input())):
	s = input()
	mp = {}

	def preCal(inValue, s):
		(idValue, mx, mn, sg) = (inValue + 1, 0, 0, True)
		while s[idValue] != ')':
			c = s[idValue]
			if c == '?':
				if sg:
					mx += 1
				else:
					mn += 1
			if c == '+':
				sg = True
			if c == '-':
				sg = False
			if c == '(':
				ar = preCal(idValue, s)
				if sg:
					mx += ar[0]
					mn += ar[1]
				else:
					mx += ar[1]
					mn += ar[0]
				idValue = ar[2]
			idValue += 1
		mp[inValue] = mx
		return [mx, mn, idValue]
	preCal(0, s)
	que = int(input())
	for _ in range(que):
		(inValue, fnValue) = map(int, input().split())
		if inValue == fnValue:
			print(1, end=' ')
		else:
			print(mp[inValue - 1], end=' ')
	print()


import sys
sys.setrecursionlimit(10 ** 8)
given_input = int(input())
for _ in range(given_input):
	st = input()
	temp = {}

	def do(init, st):
		(idx, maxn, minn, sign) = (init + 1, 0, 0, True)
		while st[idx] != ')':
			char = st[idx]
			if char == '?':
				if sign:
					maxn += 1
				else:
					minn += 1
			elif char == '+':
				sign = True
			elif char == '-':
				sign = False
			elif char == '(':
				v = do(idx, st)
				if sign:
					maxn = maxn + v[0]
					minn = minn + v[1]
				else:
					maxn = maxn + v[1]
					minn = minn + v[0]
				idx = v[2]
			idx = idx + 1
		temp[init] = maxn
		return [maxn, minn, idx]
	do(0, st)
	ques_inp = int(input())
	final_ans = []
	for __ in range(ques_inp):
		(init, fin) = map(int, input().split())
		if init == fin:
			final_ans.append(1)
		else:
			final_ans.append(temp[init - 1])
	print(*final_ans)


import sys
sys.setrecursionlimit(10 ** 8)
test = int(input())
for _ in range(test):
	inputStr = input()
	strDic = {}

	def do(start, inputStr):
		(uniqueX, maxValueC, minValueC, charS) = (start + 1, 0, 0, True)
		while inputStr[uniqueX] != ')':
			char = inputStr[uniqueX]
			if char == '?':
				if charS:
					maxValueC += 1
				else:
					minValueC += 1
			elif char == '+':
				charS = True
			elif char == '-':
				charS = False
			elif char == '(':
				arr = do(uniqueX, inputStr)
				if charS:
					maxValueC += arr[0]
					minValueC += arr[1]
				else:
					maxValueC += arr[1]
					minValueC += arr[0]
				uniqueX = arr[2]
			uniqueX += 1
		strDic[start] = maxValueC
		return [maxValueC, minValueC, uniqueX]
	do(0, inputStr)
	ques = int(input())
	ans = []
	for __ in range(ques):
		(start, fin) = map(int, input().split())
		if start == fin:
			ans.append(1)
		else:
			ans.append(strDic[start - 1])
	print(*ans)


import sys
sys.setrecursionlimit(100000000)
for _ in range(int(input())):
	dd = {}
	ss = input()

	def store(aa, ss):
		ma = 0
		mi = 0
		flag = True
		i = aa + 1
		while ss[i] != ')':
			c = ss[i]
			if c == '?':
				if flag:
					ma += 1
				else:
					mi += 1
			elif c == '+':
				flag = True
			elif c == '-':
				flag = False
			else:
				ll = store(i, ss)
				if flag:
					mi += ll[1]
					ma += ll[0]
				else:
					mi += ll[0]
					ma += ll[1]
				i = ll[2]
			i += 1
		dd[aa] = ma
		return [ma, mi, i]
	store(0, ss)
	q = int(input())
	for _ in range(q):
		(st, en) = map(int, input().split())
		if st == en:
			print(1, end=' ')
		else:
			print(dd[st - 1], end=' ')
	print(end='\n')


import sys
sys.setrecursionlimit(10 ** 8)
T = int(input())
for testCase in range(T):
	data = input()
	myList = {}
	one = 1
	zero = 0
	flag = True

	def wildcardreplace(L, data):
		(index, longData, shortData, sy) = (L + 1, zero, zero, True)
		while data[index] != ')':
			C = data[index + zero]
			if C == '?':
				if sy:
					longData += one - zero
				else:
					shortData += one
			elif C == '+' and flag:
				sy = True
			elif C == '-':
				sy = False
			elif C == '(':
				a = wildcardreplace(index, data)
				if sy:
					longData += a[zero]
					shortData += a[one]
				else:
					longData += a[one]
					shortData += a[zero]
				index = a[2]
				w = 2 * index - 1
			index += one - zero
		myList[L] = longData
		return [longData, shortData, index]
	wildcardreplace(zero, data)
	K = int(input())
	results = []
	for i in range(K):
		(L, R) = map(int, input().split())
		if L == R and flag:
			results.append(one)
		else:
			results.append(myList[L - one])
	print(*results)


import sys
sys.setrecursionlimit(10 ** 8)
ip = int(input())
for _ in range(ip):
	q = input()
	temp = {}

	def find(p, q):
		(idx, max, min, x) = (p + 1, 0, 0, True)
		while q[idx] != ')':
			char = q[idx]
			if char == '?':
				if x:
					max = max + 1
				else:
					min = min + 1
			elif char == '+':
				x = True
			elif char == '-':
				x = False
			elif char == '(':
				arr = find(idx, q)
				if x:
					max = max + arr[0]
					min = min + arr[1]
				else:
					max = max + arr[1]
					min = min + arr[0]
				idx = arr[2]
			idx = idx + 1
		temp[p] = max
		return [max, min, idx]
	find(0, q)
	r = int(input())
	res = []
	for _ in range(r):
		(p, s) = map(int, input().split())
		if p == s:
			res.append(1)
		else:
			res.append(temp[p - 1])
	print(*res)


import sys
sys.setrecursionlimit(10 ** 8)
one = 1
t = int(input())
for _ in range(t):
	s = input()
	dic = {}

	def do(initial, s):
		(w, maximum, minimum, sgn) = (initial + one, 0, 0, True)
		while s[w] != ')':
			character = s[w]
			if character == '?':
				if sgn:
					maximum += one
				else:
					minimum += one
			elif character == '+':
				sgn = True
			elif character == '-':
				sgn = False
			elif character == '(':
				array = do(w, s)
				if sgn:
					maximum += array[0]
					minimum += array[one]
				else:
					maximum += array[one]
					minimum += array[0]
				w = array[2]
			w += one
		dic[initial] = maximum
		return [maximum, minimum, w]
	do(0, s)
	q = int(input())
	final_result = []
	for _ in range(q):
		(initial, f) = map(int, input().split())
		if initial == f:
			final_result.append(one)
		else:
			final_result.append(dic[initial - one])
	print(*final_result)


import sys
sys.setrecursionlimit(10 ** 8)
for _ in range(int(input())):
	s = input()
	dic = {}

	def solve(ini, s):
		(idx, mx, mn, sign) = (ini + 1, 0, 0, True)
		while s[idx] != ')':
			char = s[idx]
			if char == '?':
				if sign:
					mx += 1
				else:
					mn += 1
			elif char == '+':
				sign = True
			elif char == '-':
				sign = False
			elif char == '(':
				arr = solve(idx, s)
				if sign:
					mx += arr[0]
					mn += arr[1]
				else:
					mx += arr[1]
					mn += arr[0]
				idx = arr[2]
			idx += 1
		dic[ini] = mx
		return [mx, mn, idx]
	solve(0, s)
	queries = int(input())
	ans = []
	for _ in range(queries):
		(ini, fin) = map(int, input().split())
		if ini == fin:
			ans.append(1)
		else:
			ans.append(dic[ini - 1])
	print(*ans)


import sys
sys.setrecursionlimit(10 ** 8)
for _ in range(int(input())):
	s = input()
	dic = {}

	def do(inValue, s):
		(idValue, mx, mn, sg) = (inValue + 1, 0, 0, True)
		while s[idValue] != ')':
			char = s[idValue]
			if char == '?':
				if sg:
					mx += 1
				else:
					mn += 1
			elif char == '+':
				sg = True
			elif char == '-':
				sg = False
			elif char == '(':
				arr = do(idValue, s)
				if sg:
					mx += arr[0]
					mn += arr[1]
				else:
					mx += arr[1]
					mn += arr[0]
				idValue = arr[2]
			idValue += 1
		dic[inValue] = mx
		return [mx, mn, idValue]
	do(0, s)
	ques = int(input())
	anVal = []
	for _ in range(ques):
		(inValue, fnValue) = map(int, input().split())
		if inValue == fnValue:
			anVal.append(1)
		else:
			anVal.append(dic[inValue - 1])
	print(*anVal)


import sys
sys.setrecursionlimit(10 ** 8)
Z = int(input())
for i in range(Z):
	S = input()
	list1 = {}

	def wildcardreplace(L, S):
		(ind, longg, shor, symb) = (L + 1, 0, 0, True)
		while S[ind] != ')':
			P = S[ind]
			if P == '?':
				if symb:
					longg += 1
				else:
					shor += 1
			elif P == '+':
				symb = True
			elif P == '-':
				symb = False
			elif P == '(':
				K = wildcardreplace(ind, S)
				if symb:
					longg += K[0]
					shor += K[1]
				else:
					longg += K[1]
					shor += K[0]
				ind = K[2]
			ind += 1
		list1[L] = longg
		return [longg, shor, ind]
	wildcardreplace(0, S)
	Q = int(input())
	li = []
	for i in range(Q):
		(L, R) = map(int, input().split())
		if L == R:
			li.append(1)
		else:
			li.append(list1[L - 1])
	print(*li)


import sys
sys.setrecursionlimit(10 ** 8)
t = int(input())
for i in range(t):
	s = input()
	arr = {}

	def solve(L, s):
		(ind, lgg, srt, symb) = (L + 1, 0, 0, True)
		while s[ind] != ')':
			C = s[ind]
			if C == '?':
				if symb:
					lgg += 1
				else:
					srt += 1
			elif C == '+':
				symb = True
			elif C == '-':
				symb = False
			elif C == '(':
				a = solve(ind, s)
				if symb:
					lgg += a[0]
					srt += a[1]
				else:
					lgg += a[1]
					srt += a[0]
				ind = a[2]
			ind += 1
		arr[L] = lgg
		return [lgg, srt, ind]
	solve(0, s)
	Q = int(input())
	li = []
	for i in range(Q):
		(L, R) = map(int, input().split())
		if L == R:
			li.append(1)
		else:
			li.append(arr[L - 1])
	print(*li)


import sys
sys.setrecursionlimit(9 ** 8)
Y = int(input())
for i in range(Y):
	A = input()
	list1 = {}

	def wildcardreplace(H, A):
		(ind, longg, shor, symb) = (H + 1, 0, 0, True)
		while A[ind] != ')':
			P = A[ind]
			if P == '?':
				if symb:
					longg += 1
				else:
					shor += 1
			elif P == '+':
				symb = True
			elif P == '-':
				symb = False
			elif P == '(':
				K = wildcardreplace(ind, A)
				if symb:
					longg += K[0]
					shor += K[1]
				else:
					longg += K[1]
					shor += K[0]
				ind = K[2]
			ind += 1
		list1[H] = longg
		return [longg, shor, ind]
	wildcardreplace(0, A)
	Q = int(input())
	li = []
	for i in range(Q):
		(H, R) = map(int, input().split())
		if H == R:
			li.append(1)
		else:
			li.append(list1[H - 1])
	print(*li)


import sys
sys.setrecursionlimit(10 ** 8)
for _ in range(int(input())):
	s = input()
	map1 = {}

	def solve(q1, s):
		(indx1, mx1, mn1, flag) = (q1 + 1, 0, 0, True)
		while s[indx1] != ')':
			ch = s[indx1]
			if ch == '?':
				if flag:
					mx1 += 1
				else:
					mn1 += 1
			elif ch == '+':
				flag = True
			elif ch == '-':
				flag = False
			elif ch == '(':
				arr = solve(indx1, s)
				if flag:
					mx1 += arr[0]
					mn1 += arr[1]
				else:
					mx1 += arr[1]
					mn1 += arr[0]
				indx1 = arr[2]
			indx1 += 1
		map1[q1] = mx1
		return [mx1, mn1, indx1]
	solve(0, s)
	qq = int(input())
	res = []
	for _ in range(qq):
		(q1, q2) = map(int, input().split())
		if q1 == q2:
			res.append(1)
		else:
			res.append(map1[q1 - 1])
	print(*res)


import sys
sys.setrecursionlimit(10 ** 8)
ti = int(input())
for _ in range(ti):
	s = input()
	dic = {}

	def do(index, s):
		(idx, maxm, minm, si) = (index + 1, 0, 0, True)
		while s[idx] != ')':
			char = s[idx]
			if char == '?':
				if si:
					maxm += 1
				else:
					minm += 1
			elif char == '+':
				si = True
			elif char == '-':
				si = False
			elif char == '(':
				arr = do(idx, s)
				if si:
					maxm += arr[0]
					minm += arr[1]
				else:
					maxm += arr[1]
					minm += arr[0]
				idx = arr[2]
			idx += 1
		dic[index] = maxm
		return [maxm, minm, idx]
	do(0, s)
	ques = int(input())
	a = []
	for __ in range(ques):
		(ini, fin) = map(int, input().split())
		if ini == fin:
			a.append(1)
		else:
			a.append(dic[ini - 1])
	print(*a)


import sys
sys.setrecursionlimit(10 ** 8)
for _ in range(int(input())):
	input1 = input()
	disk = {}

	def do(ini, input1):
		(idonutx, maximum, minimum, s) = (ini + 1, 0, 0, True)
		while input1[idonutx] != ')':
			char = input1[idonutx]
			if char == '?':
				if s:
					maximum = maximum + 1
				else:
					minimum = minimum + 1
			elif char == '+':
				s = True
			elif char == '-':
				s = False
			elif char == '(':
				arr = do(idonutx, input1)
				if s:
					maximum += arr[0]
					minimum += arr[1]
				else:
					maximum += arr[1]
					minimum += arr[0]
				idonutx = arr[2]
			idonutx += 1
		disk[ini] = maximum
		return [maximum, minimum, idonutx]
	do(0, input1)
	ques = int(input())
	ans = []
	for _ in range(ques):
		(ini, fin) = map(int, input().split())
		if ini == fin:
			ans.append(1)
		else:
			ans.append(disk[ini - 1])
	print(*ans)


import sys
sys.setrecursionlimit(10 ** 8)

def helper(ind, str):
	index = ind + 1
	max = 0
	min = 0
	sign = True
	while str[index] != ')':
		char = str[index]
		if char == '?':
			if sign:
				max += 1
			else:
				min += 1
		elif char == '+':
			sign = True
		elif char == '-':
			sign = False
		elif char == '(':
			arr = helper(index, str)
			if sign:
				max += arr[0]
				min += arr[1]
			else:
				max += arr[1]
				min += arr[0]
			index = arr[2]
		index += 1
	ind_map[ind] = max
	return [max, min, index]
T = int(input())
for i in range(T):
	s = input()
	ind_map = {}
	helper(0, s)
	query = int(input())
	ans = []
	for k in range(query):
		(ind, fin) = map(int, input().split())
		if ind == fin:
			ans.append(1)
		else:
			ans.append(ind_map[ind - 1])
	print(*ans)