You may have tried your level best to help Chef but Dr Doof has managed to come up with his masterplan in the meantime. Sadly, you have to help Chef once again. Dr Doof has designed a parenthesis-inator. It throws a stream of $N$ brackets at the target, $1$ bracket per second. The brackets can either be opening or closing. Chef appears in front of the stream at time $t$. If Chef faces an opening bracket, he gets hit. However, if he faces a closing bracket, he may choose to let it pass through him (Chef is immune to closing brackets). Chef gets a chance to counter attack Doof as soon as he finds a balanced non-empty bracket sequence. Help Chef by providing him the minimum time $x$ at which he will be able to launch his counter attack. If Chef is unable to counter attack, answer $-1$.

Formally, you are given a string $S$ of length $N$ consisting only of opening brackets $($ and closing brackets $)$. The substring of $S$ starting at index $L$ and ending at index $R$, i.e. $S_{L} S_{L+1} \ldots S_{R}$ is denoted by $S[L, R]$ . Consider $Q$ cases. In the $i^{\text{th}}$ case, Chef appears at time $t_{i}$ $(1 ≤ t_{i} ≤ N)$ and faces all characters from index $t_{i}$ to $N$. Find the minimum index $x$ $(t_{i} ≤ x ≤ N)$ such that the substring $S[t_{i}, x]$ contains a non-empty balanced bracket subsequence containing the same number of opening brackets as $S[t_{i}, x]$ (i.e., you cannot remove any opening bracket from the substring). If such an $x$ does not exist, print $-1$.

A string $X$ is called a subsequence of a string $Y$ if it is possible to obtain $X$ by erasing some (possibly zero) characters from $Y$ without changing the order of the remaining characters.

A balanced bracket sequence is defined as:  
an empty string is a balanced bracket sequence.
if $s$ is a balanced bracket sequence, then so is $(s)$.
if $s$ and $t$ are balanced bracket sequences, then so is $st$.

$Note :-$ The input files are large. The use of Fast I/O is recommended.

------ Input ------

The first line contains a single integer $T$ denoting the number of testcases.
The first line of each test case contains the string $S$.
The next line contains a single integer $Q$ denoting the number of cases to consider.
The next line contains $Q$ space separated integers, each denoting $t_{i}$.

------ Output ------

For each query, print the minimum value of $x$ in a separate line. If no such $x$ exists, print $-1$.

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

$1 ≤ T ≤ 10^{3}$
$1 ≤ |S| ≤ 10^{7}$
$1 ≤ Q ≤ 10^{6}$
$1 ≤ t_{i} ≤ N$
Every character of $S$ is either $($ or $)$.
Sum of $|S|$ and $Q$ over all testcases for a particular test file does not exceed $10^{7}$ and $10^{6}$ respectively.

----- Sample Input 1 ------ 
1
)())((()
3
1 7 6
----- Sample Output 1 ------ 
3
8
-1
----- explanation 1 ------ 
For the first query, Chef chooses to let $S_{1}$ pass through him, gets hit by $S_{2}$ and finally completes a balanced bracket sequence by adding $S_{3}$ to $S_{2}$ at time $x$ = $3$.

Difficulty: MEDIUM_HARD
Tags: String algorithms

Constructive algorithms

Data structures

Ad-hoc
Skill types: Data structures

Starter code:

Solutions:
for _ in range(int(input())):
	s = input()
	Q = int(input())
	q = list(map(int, input().split()))
	next = [-1] * len(s)
	stack = []
	for i in range(len(s)):
		if s[i] == '(':
			stack.append(i)
		elif stack:
			next[stack.pop()] = i + 1
	last = -1
	for i in range(len(s) - 1, -1, -1):
		if s[i] == '(':
			last = next[i]
		else:
			next[i] = last
	for i in range(Q):
		print(next[q[i] - 1])


for tc in range(int(input())):
	S = input()
	N = len(S)
	next = [-1] * N
	stack = []
	for i in range(N):
		if S[i] == '(':
			stack.append(i)
		elif stack:
			next[stack.pop()] = i + 1
	last = -1
	for i in range(N - 1, -1, -1):
		if S[i] == '(':
			last = next[i]
		else:
			next[i] = last
	Q = int(input())
	q = list(map(int, input().split()))
	for i in range(Q):
		print(next[q[i] - 1])


for _ in range(int(input())):
	s = input()
	stack = []
	a = [-1 for i in range(len(s))]
	l = -1
	for i in range(len(s) - 1, -1, -1):
		if s[i] == ')':
			stack.append(i)
			a[i] = l
		elif stack:
			l = a[i] = stack.pop()
		else:
			l = -1
	q = int(input())
	for i in list(map(int, input().split())):
		if a[i - 1] == -1:
			print(-1)
		else:
			print(a[i - 1] + 1)


from bisect import bisect_left
I = input
t = int(I())
for _ in range(t):
	s = I()
	a = [i for (i, x) in enumerate(s, 1) if x == '(']
	b = [-1] * (len(a) + 1)
	st = []
	j = 0
	for (i, x) in enumerate(s, 1):
		if x == '(':
			st.append(j)
			j += 1
		elif st:
			b[st.pop()] = i
	I()
	for t in map(int, I().split()):
		print(b[bisect_left(a, t)])


from bisect import bisect_left
I = input
t = int(I())
for _ in range(t):
	(a, b, s) = ([], [], [])
	d = {}
	for (i, x) in enumerate(I(), 1):
		if x == '(':
			a.append(i)
			b.append(-1)
			s.append(i)
		elif s:
			b[bisect_left(a, s.pop())] = i
	b.append(-1)
	I()
	for t in map(int, I().split()):
		print(b[bisect_left(a, t)])


try:
	T = int(input())
	for t in range(T):
		s = input()
		n = len(s)
		q = int(input())
		a = list(map(int, input().split()))
		ans = [-1] * n
		stack = []
		for i in range(n):
			if s[i] == '(':
				stack.append(i)
			elif stack != []:
				ans[stack.pop()] = i + 1
		last = -1
		for i in range(n - 1, -1, -1):
			if s[i] == '(':
				last = ans[i]
			else:
				ans[i] = last
		for i in range(q):
			print(ans[a[i] - 1])
except:
	pass


for _ in range(int(input())):
	s = input()
	stack = []
	complete = [-1] * len(s)
	for i in range(len(s)):
		if s[i] == '(':
			stack.append(i)
		elif stack:
			complete[stack.pop()] = i + 1
	next_opening_bracket = -1
	for i in range(len(s) - 1, -1, -1):
		if s[i] == '(':
			next_opening_bracket = complete[i]
		else:
			complete[i] = next_opening_bracket
	q = int(input())
	qi = [int(x) for x in input().split()]
	for ti in qi:
		v = complete[ti - 1]
		print(v)


t = int(input())
while t:
	s = input()
	q = int(input())
	arr = list(map(int, input().split()))
	(dic, stack) = ({}, [])
	(count, get) = (0, -1)
	for i in range(len(s) - 1, -1, -1):
		if s[i] == ')':
			dic[i + 1] = get
			stack.append(i + 1)
		elif len(stack):
			get = stack.pop()
			dic[i + 1] = get
		else:
			dic[i + 1] = -1
			get = -1
	for i in arr:
		print(dic[i])
	t -= 1


for t in range(int(input())):
	s = input()
	n = len(s)
	next = [-1] * n
	stack = []
	for i in range(n):
		if s[i] == '(':
			stack.append(i)
		elif stack:
			next[stack.pop()] = i + 1
	last = -1
	for i in range(n - 1, -1, -1):
		if s[i] == '(':
			last = next[i]
		else:
			next[i] = last
	q = int(input())
	arr = list(map(int, input().split()))
	for i in range(q):
		print(next[arr[i] - 1])


import sys, math, numpy as np
from sys import stdin, stdout
mod = int(1000000000.0 + 7)
from collections import deque, defaultdict
from copy import deepcopy
from math import ceil, floor, inf, sqrt, factorial, gcd, log2
ii1 = lambda : int(stdin.readline().strip())
is1 = lambda : stdin.readline().strip()
iia = lambda : list(map(int, stdin.readline().strip().split()))
isa = lambda : stdin.readline().strip().split()
for _ in range(ii1()):
	s = is1()
	n = len(s)
	stack = []
	ans = [-1] * n
	i = n - 1
	while i >= 0:
		if s[i] == ')':
			stack.append(i)
		elif stack:
			ans[i] = stack.pop() + 1
		i -= 1
	i = n - 2
	while i >= 0:
		if ans[i] == -1 and s[i] == ')':
			ans[i] = ans[i + 1]
		i -= 1
	q = ii1()
	query = iia()
	for i in query:
		print(ans[i - 1])


for _ in range(int(input())):
	s = list(input())
	q = int(input())
	l = list(map(int, input().split()))
	num = []
	num1 = [-1] * len(s)
	(cl, f) = (0, -1)
	for i in range(len(s) - 1, -1, -1):
		if s[i] == ')':
			num.append(i + 1)
			cl += 1
			if i < len(s) - 1:
				num1[i] = num1[i + 1]
		elif cl > 0:
			num1[i] = num[-1]
			num.pop()
			cl -= 1
	for i in l:
		print(num1[i - 1])


t = int(input())
while t > 0:
	s = input()
	q = int(input())
	l = [int(x) for x in input().split()]
	p = [-2] * len(s)
	h = []
	for i in range(0, len(s)):
		if s[i] == '(':
			h.append(i)
		elif h:
			p[h.pop()] = i
	le = -2
	for i in range(len(s) - 1, -1, -1):
		if s[i] == '(':
			le = p[i]
		else:
			p[i] = le
	for i in range(0, q):
		if p[l[i] - 1] == -2:
			print('-1')
		else:
			print(p[l[i] - 1] + 1)
	t = t - 1


import sys
input = sys.stdin.readline
I = lambda : list(map(str, input().split()))
(n,) = I()
n = int(n)
while n:
	(arr,) = I()
	(m,) = I()
	q = I()
	stack = []
	openb = {}
	prev = 1
	for i in range(len(arr)):
		openb[i + 1] = -1
		if arr[i] == '(':
			stack.append(i)
		elif len(stack):
			new = stack.pop() + 1
			openb[new] = i + 1
			new -= 1
			while True and new:
				if arr[new - 1] == ')':
					openb[new] = i + 1
					new -= 1
				else:
					break
	for j in q:
		print(openb[int(j)])
	n -= 1


def check(string):
	n = len(string)
	default = -1
	main = []
	stack = []
	for i in range(n):
		if string[i] == ')':
			main.append(default)
			stack.append(i)
		elif stack:
			default = n - stack.pop()
			main.append(default)
		else:
			default = -1
			main.append(default)
	return main[::-1]
import sys
input = sys.stdin.readline
for _ in range(int(input())):
	string = str(input().strip())
	n = int(input())
	indexes = [int(i) for i in input().split()]
	ans = check(string[::-1])
	for i in indexes:
		print(ans[i - 1])


t = int(input())
for _ in range(t):
	s = input()
	n = len(s)
	ans = [-1] * n
	l = []
	for i in range(n):
		if s[i] == '(':
			l.append(i)
		else:
			ans[i] = 0
			if len(l):
				ans[l.pop()] = i
	op = -1
	for i in range(len(ans) - 1, -1, -1):
		if ans[i] == 0:
			ans[i] = op
		else:
			op = ans[i]
	q = int(input())
	arr = list(map(int, input().split()))
	for i in arr:
		if ans[i - 1] == -1:
			print(-1)
		else:
			print(ans[i - 1] + 1)


from sys import stdin, stdout
from math import gcd, ceil, sqrt
from collections import Counter
from bisect import bisect_left, bisect_right
ii1 = lambda : int(stdin.readline().strip())
is1 = lambda : stdin.readline().strip()
iia = lambda : list(map(int, stdin.readline().strip().split()))
isa = lambda : stdin.readline().strip().split()
mod = 1000000007
tc = ii1()
for _ in range(tc):
	s = is1()
	time = {}
	stack = []
	for (i, j) in enumerate(s):
		if j == '(':
			stack.append(i)
		elif len(stack):
			time[stack.pop()] = i + 1
	last = -1
	for i in range(len(s))[::-1]:
		if s[i] == '(':
			last = time.get(i, -1)
		else:
			time[i] = last
	ii1()
	q = iia()
	for i in q:
		print(time.get(i - 1, -1))


t = int(input())
for tc in range(t):
	s = input()
	q = int(input())
	qrr = list(map(int, input().split()))
	n = len(s)
	ans = [-1] * n
	stack = []
	for i in range(n):
		if s[i] == '(':
			stack.append(i)
		else:
			ans[i] = 0
			if stack:
				ans[stack.pop()] = i
	op = -1
	for i in range(len(ans) - 1, -1, -1):
		if ans[i] == 0:
			ans[i] = op
		else:
			op = ans[i]
	for i in qrr:
		if ans[i - 1] == -1:
			print('-1')
		else:
			print(ans[i - 1] + 1)


def clbrkt(s, n):
	flow = [-1] * n
	stack = []
	for i in range(n):
		if s[i] == '(':
			stack.append(i)
		elif stack:
			flow[stack.pop()] = i + 1
	last = -1
	for i in range(n - 1, -1, -1):
		if s[i] == '(':
			last = flow[i]
		else:
			flow[i] = last
	return flow
t = int(input())
for _ in range(t):
	s = input()
	n = len(s)
	q = int(input())
	qs = list(map(int, input().split()))
	res = clbrkt(s, n)
	for i in qs:
		print(res[i - 1])


from collections import deque
for _ in range(int(input())):
	s = input()
	l = len(s)
	n = int(input())
	x = list(map(int, input().split()))
	st = list()
	qd = dict()
	xl = deque()
	for i in range(0, l):
		if st and s[i] == ')' and (st[-1][1] == '('):
			qd[st.pop()[0]] = i
		else:
			st.append((i, s[i]))
		if s[i] == '(':
			xl.append(i)
	xl.extend([l - 1] * 2)
	p = xl.popleft()
	nx = dict()
	for i in range(l):
		nx[i] = p
		if i == p:
			p = xl.popleft()
	for xx in range(n):
		i = x[xx]
		if i == l:
			print(-1)
			continue
		sp = nx[i - 1] + 1
		if sp == l:
			print(-1)
			continue
		if sp - 1 in qd:
			print(qd[sp - 1] + 1)
		else:
			print(-1)


for _ in range(int(input())):
	s = list(input())
	n = len(s)
	cl = dict()
	tp = []
	ans = [-1] * (n + 1)
	for i in range(n - 1, -1, -1):
		if s[i] == ')':
			ans[i] = ans[i + 1]
			tp.append(i)
		elif len(tp) != 0:
			k = tp.pop()
			ans[i] = k + 1
	k = int(input())
	arr = list(map(int, input().split()))
	for j in arr:
		print(ans[j - 1])


for _ in range(int(input())):
	s = input()
	q = int(input())
	lst = list(map(int, input().split()))
	arr = [-1] * len(s)
	stack = []
	for i in range(len(s)):
		if s[i] == '(':
			stack.append(i)
		else:
			arr[i] = 0
			if len(stack):
				arr[stack.pop()] = i
	res = -1
	for i in range(len(s) - 1, -1, -1):
		if arr[i] == 0:
			arr[i] = res
		else:
			res = arr[i]
	for i in lst:
		if arr[i - 1] == -1:
			print(-1)
		else:
			print(arr[i - 1] + 1)


from collections import deque
from sys import stdout, stdin
input = stdin.readline
out = stdout.write
for _ in range(int(input())):
	s = str(input())
	m = int(input())
	a = list(map(int, input().split()))
	d = deque()
	b = [-1] * len(s)
	l = -1
	for i in range(len(s) - 1, -1, -1):
		if s[i] == ')':
			d.append(i)
			b[i] = l
		elif len(d) != 0:
			b[i] = d[-1]
			d.pop()
			l = b[i]
		else:
			l = -1
	for i in range(m):
		if b[a[i] - 1] == -1:
			print(-1)
		else:
			print(b[a[i] - 1] + 1)


for _ in range(int(input())):
	s = input()
	n = len(s)
	ans = [0] * (n + 1)
	st = []
	last = -1
	for i in range(n - 1, -1, -1):
		if s[i] == '(':
			if len(st) == 0:
				ans[i + 1] = -1
				last = -1
			else:
				ans[i + 1] = st[-1]
				last = ans[i + 1]
				st.pop(-1)
		else:
			ans[i + 1] = last
			st.append(i + 1)
	q = int(input())
	qt = list(map(int, input().split()))
	for i in qt:
		print(ans[i])


for _ in range(int(input())):
	s = input()
	n = len(s)
	arr = [-1] * (n + 1)
	store = []
	for t in range(n - 1, -1, -1):
		if s[t] == '(':
			if store == []:
				arr[t] = -1
			else:
				a = store.pop()
				arr[t] = a + 1
		else:
			arr[t] = arr[t + 1]
			store.append(t)
	n = input()
	l = list(map(int, input().split()))
	for a in l:
		print(arr[a - 1])


import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T):
	s = input()
	q = int(input())
	t = list(map(int, input().split()))
	stack = []
	val = [-1 for i in range(len(s))]
	last_open = -1
	for i in range(len(s) - 2, -1, -1):
		if s[i] == ')':
			stack.append(i)
			val[i] = last_open
		elif len(stack) != 0:
			val[i] = stack[-1]
			stack.pop()
			last_open = val[i]
		else:
			last_open = -1
	for i in range(q):
		if val[t[i] - 1] == -1:
			print(-1)
		else:
			print(val[t[i] - 1] + 1)


mex = 10 ** 7 + 5
for _ in range(int(input())):
	s = input()
	n = len(s)
	q = int(input())
	arr = list(map(int, input().split()))
	close = []
	ans = [-1 for i in range(n + 5)]
	for i in range(n - 1, -1, -1):
		if s[i] == '(':
			if close == []:
				ans[i] = -1
			else:
				ans[i] = close[-1] + 1
				close.pop()
		else:
			ans[i] = ans[i + 1]
			close.append(i)
	for i in arr:
		print(ans[i - 1])


from collections import *
from bisect import *
import sys
input = sys.stdin.readline
t = int(input())
q = 998244353
while t:
	t -= 1
	s = input().rstrip('\n')
	q = int(input())
	l = []
	an = [-2] * len(s)
	n = len(s)
	for i in range(n - 1, -1, -1):
		if s[i] == '(':
			if len(l):
				an[i] = l.pop()
		else:
			l.append(i)
			if i != n - 1:
				an[i] = an[i + 1]
	q = list(map(int, input().split()))
	for i in q:
		print(an[i - 1] + 1)


import bisect
for _ in range(int(input())):
	s = str(input())
	n = len(s)
	l = list(s)
	q = int(input())
	lq = list(map(int, input().split()))
	l1 = [0] * (n + 1)
	st = []
	l1[n] = -1
	if s[-1] == ')':
		st.append(n)
	for i in range(n - 1, 0, -1):
		if l[i - 1] == '(':
			if len(st) == 0:
				l1[i] = -1
			else:
				x = st[-1]
				st.pop()
				l1[i] = x
		else:
			l1[i] = l1[i + 1]
			st.append(i)
	for i in range(q):
		print(l1[lq[i]])


import sys
import bisect as bi
import math
from collections import defaultdict as dd
input = sys.stdin.readline

def cin():
	return map(int, sin().split())

def ain():
	return list(map(int, sin().split()))

def sin():
	return input()

def inin():
	return int(input())
for _ in range(inin()):
	s = sin().strip()
	q = inin()
	a = ain()
	n = len(s)
	store = [0] * n
	store1 = [-1] * n
	f = 0
	d = dd(int)
	store[0] = 1 if s[0] == '(' else -1
	d[store[0]] = 1
	for i in range(1, n):
		if s[i] == '(':
			store[i] = store[i - 1] + 1
			d[store[i]] = i + 1
		else:
			store[i] = store[i - 1] - 1
			if d[store[i - 1]]:
				store1[d[store[i - 1]] - 1] = i + 1
	post = [-1] * n
	if n == 1 or (n == 2 and s != '()'):
		f = 1
	for i in range(n - 2, -1, -1):
		if s[i] == '(':
			if store1[i] != -1:
				post[i] = store1[i]
		else:
			post[i] = post[i + 1]
	for i in a:
		if f:
			print(-1)
		else:
			print(post[i - 1])


T = int(input())
for _ in range(T):
	s = input()
	_ = input()
	stack = []
	nextOpen = [-1 for _ in range(len(s))]
	closing = [-1 for _ in range(len(s))]
	nextO = len(s) + 1
	for i in range(len(s) - 1, -1, -1):
		if s[i] == '(':
			nextO = i
			if stack:
				closing[i] = stack.pop()
		else:
			stack.append(i)
		nextOpen[i] = nextO
	for t in map(int, input().split()):
		t -= 1
		t = nextOpen[t]
		if t < len(s):
			res = closing[t]
			print(res + 1 if res >= 0 else -1)
		else:
			print(-1)


from sys import stdin, stdout
for t in range(int(stdin.readline())):
	s = str(stdin.readline())
	q = int(stdin.readline())
	a = list(map(int, stdin.readline().split()))
	d = {}
	stc = []
	p = -1
	for i in range(len(s) - 1, -1, -1):
		if s[i] == ')':
			stc.append(i)
			d[i + 1] = p
		elif s[i] == '(':
			if len(stc) >= 1:
				d[i + 1] = stc[-1] + 1
				p = d[i + 1]
				stc.pop()
			else:
				d[i + 1] = -1
				p = d[i + 1]
	for i in a:
		print(d[i])


try:
	tt = int(input())
	while tt:
		tt = tt - 1
		s = input()
		(st1, dicti, i) = ([], {}, 1)
		for j in s:
			if j == '(':
				st1.append(i)
			elif st1:
				h = st1.pop() - 2
				dicti[h + 2] = i
				while h >= 0 and s[h] == ')':
					dicti[h + 1] = i
					h -= 1
			i += 1
		q = int(input())
		t = list(map(int, input().split()))
		for i in t:
			if i in dicti.keys():
				print(dicti[i])
			else:
				print(-1)
except:
	pass


t = int(input())
for _ in range(t):
	s = input()
	s = list(s)
	n = len(s)
	answer = []
	stack = []
	stack2 = []
	for i in range(len(s) - 1, -1, -1):
		if s[i] == ')':
			if answer == []:
				answer = [-1]
				stack2.append(i)
				stack.append(')')
				continue
			stack2.append(i)
			answer.append(answer[-1])
			stack.append(')')
		elif stack2 == []:
			answer.append(-1)
			stack.append('(')
		else:
			stack.pop()
			e = stack2[-1]
			stack2.pop()
			answer.append(e + 1)
	answer.reverse()
	q = int(input())
	W = list(map(int, input().split()))
	for i in range(q):
		w = W[i]
		print(answer[w - 1])


for _ in range(int(input())):
	st = input()
	q = int(input())
	qi = list(map(int, input().split()))
	n = len(st)
	tracker = 0
	ans = [-1] * n
	stack = []
	for i in range(n - 1, -1, -1):
		if st[i] == ')':
			stack.append(i + 1)
			if i != n - 1:
				ans[i] = ans[i + 1]
			tracker -= 1
		elif tracker < 0 and st[i] == '(':
			ans[i] = stack.pop()
			tracker += 1
	for i in range(q):
		print(ans[qi[i] - 1])


try:

	def findans(s):
		(l, val, r) = ([], {}, [])
		for (i, kk) in enumerate(s):
			if kk == '(':
				l.append(i + 1)
			elif l:
				x = l.pop()
				val[x] = i + 1
				x -= 2
				while x >= 0 and s[x] == ')':
					val[x + 1] = i + 1
					x -= 1
		return val
	for ii in range(int(input())):
		b = input()
		dic = findans(b)
		n = int(input())
		q = list(map(int, input().split()))
		for jj in q:
			print(dic.get(jj, -1))
except:
	pass


from sys import stdin, stdout
t = int(stdin.readline())
while t:
	t -= 1
	string = str(stdin.readline())
	q = int(stdin.readline())
	a = list(map(int, stdin.readline().split()))
	pos = 0
	l = {}
	stack = []
	pos = -1
	for j in range(len(string) - 1, -1, -1):
		if string[j] == ')':
			stack.append(j)
			l[j + 1] = pos
		elif string[j] == '(':
			if len(stack) >= 1:
				l[j + 1] = stack[-1] + 1
				pos = l[j + 1]
				stack.pop()
			else:
				l[j + 1] = -1
				pos = l[j + 1]
	for item in a:
		print(l[item])


def find_min(s, queries):
	stack = []
	balancing = [-1] * len(s)
	op = [-1] * len(s)
	last_opening = -1
	for i in range(len(s) - 1, -1, -1):
		if s[i] == ')':
			op[i] = last_opening
		else:
			last_opening = i
	for i in range(len(s)):
		if s[i] == ')':
			if len(stack) != 0:
				balancing[stack[-1]] = i
				del stack[-1]
		else:
			stack.append(i)
	for query in queries:
		q = query - 1
		if s[q] == ')':
			if op[q] == -1:
				print(-1)
				continue
			else:
				q = op[q]
		if balancing[q] == -1:
			print(-1)
		else:
			print(balancing[q] + 1)
T = int(input())
while T != 0:
	s = input()
	q = int(input())
	queries = [int(a) for a in input().split(' ')]
	find_min(s, queries)
	T -= 1


from collections import deque
from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	s = list(input())
	n = len(s)
	ans = [0] * n
	x = 0
	y = 0
	a = n - 1
	b = n - 1
	stack = deque([])
	prev = -1
	while a >= 0:
		if s[a] == ')':
			stack.append(a)
			ans[a] = prev
		elif len(stack) == 0:
			ans[a] = -1
			prev = -1
		else:
			prev = stack[-1] + 1
			ans[a] = prev
			stack.pop()
		a -= 1
	q = int(input())
	x = list(map(int, input().split()))
	for i in x:
		i = i - 1
		print(ans[i])


import math
from collections import *
import sys
from functools import reduce
from itertools import groupby

def get_ints():
	return map(int, input().strip().split())

def get_list():
	return list(get_ints())

def get_string():
	return list(input().strip().split())

def printxsp(*args):
	return print(*args, end='')

def printsp(*args):
	return print(*args, end=' ')
DIRECTIONS = [[0, 1], [0, -1], [1, 0], [1, -1]]
NEIGHBOURS = [(i, j) for i in range(-1, 2) for j in range(-1, 2) if i != 0 or j != 0]
OrdUnicode_a = ord('a')
OrdUnicode_A = ord('A')
CAPS_ALPHABETS = {chr(i + OrdUnicode_A): i for i in range(26)}
SMOL_ALPHABETS = {chr(i + OrdUnicode_a): i for i in range(26)}
MOD_JOHAN = int(1000000000.0) + 7
MOD_LIGHT = 998244353
INFINITY = float('inf')
MAXN_EYEPATCH = int(100000.0) + 1
MAXN_FULLMETAL = 501
for _testcases_ in range(int(input())):
	s = input()
	n = len(s)
	input()
	q = get_list()
	ans = [-1] * (n + 1)
	stack = []
	for (i, v) in enumerate(s):
		if v == '(':
			stack.append(i + 1)
		elif len(stack) > 0:
			ans[stack.pop()] = i + 1
	touka = -1
	for i in range(n, 0, -1):
		if s[i - 1] == '(':
			if touka == -1:
				touka = ans[i]
			else:
				touka = ans[i]
		else:
			ans[i] = touka
	for i in q:
		print(ans[i])


t = int(input())
for _ in range(t):
	s = input().strip()
	(li, stk, tmp) = ([-1] * len(s), [], [])
	for i in range(len(s)):
		if len(stk):
			if s[i] == '(':
				while len(tmp):
					stk.append(tmp.pop())
				stk.append(i)
			elif s[stk[-1]] == '(':
				li[stk[-1]] = i
				v = stk.pop()
				while len(stk) != 0:
					if s[stk[-1]] == ')':
						li[stk[-1]] = v
						stk.pop()
					else:
						break
				tmp.append(i)
			else:
				stk.append(i)
			pass
		elif s[i] == '(':
			while len(tmp) != 0:
				stk.append(tmp.pop())
			stk.append(i)
		else:
			stk.append(i)
	q = int(input())
	for i in map(int, input().split()):
		ind = i - 1
		while li[ind] != -1 and s[li[ind]] != ')':
			ind = li[ind]
		if li[ind] != -1:
			print(li[ind] + 1)
		else:
			print(-1)


for _ in range(int(input())):
	s = input()
	n = int(input())
	l = list(map(int, input().split()))
	count = 0
	stk = []
	last = -1
	store = [0] * len(s)
	for i in range(len(s) - 1, -1, -1):
		if s[i] == ')':
			stk.append(i + 1)
			if last == -1:
				store[i] = -1
			else:
				store[i] = last
		elif len(stk) == 0:
			store[i] = -1
			last = -1
		else:
			x = stk.pop()
			store[i] = x
			last = x
	for i in range(len(l)):
		print(store[l[i] - 1])


import sys
import math
from collections import defaultdict, Counter
input = sys.stdin.readline

def print(x):
	sys.stdout.write(str(x) + '\n')
t = int(input())
for i in range(t):
	s = input().strip()
	c = 0
	v = [0] * len(s)
	st = []
	prev = -2
	c1 = 0
	for j in range(len(s) - 1, -1, -1):
		if s[j] == ')':
			v[j] = prev
			st.append(j)
		else:
			c1 += 1
			c += 1
			if st:
				v[j] = st.pop()
			else:
				v[j] = -2
			prev = v[j]
	q1 = int(input())
	q = list(map(int, input().split()))
	for j in q:
		print(v[j - 1] + 1)


from sys import stdin, stdout
INF = 100000000000.0
import bisect

def get_int():
	return int(stdin.readline().strip())

def get_ints():
	return map(int, stdin.readline().strip().split())

def get_array():
	return list(map(int, stdin.readline().strip().split()))

def get_string():
	return stdin.readline().strip()

def op(c):
	return stdout.write(c)
from collections import defaultdict
import math
for _ in range(int(stdin.readline())):
	s = get_string()
	n = len(s)
	ans = [0] * (n + 1)
	st = []
	last = -1
	for i in range(n - 1, -1, -1):
		if s[i] == '(':
			if len(st) == 0:
				ans[i + 1] = -1
				last = -1
			else:
				ans[i + 1] = st[-1]
				last = ans[i + 1]
				st.pop(-1)
		else:
			ans[i + 1] = last
			st.append(i + 1)
	q = get_int()
	qt = get_array()
	for i in qt:
		print(ans[i])


for t in range(int(input())):
	s = input()
	q = int(input())
	query = list(map(int, input().split()))
	n = len(s)
	store = {}
	stack = []
	for (ind, b) in enumerate(list(s)):
		if b == '(':
			stack.append(ind)
		elif len(stack) == 0:
			pass
		else:
			el = stack[-1]
			stack.pop(-1)
			if s[el] == '(':
				store[el] = ind
				el = el - 1
				while el >= 0 and s[el] == ')':
					store[el] = ind
					el = el - 1
			else:
				pass
	for start in query:
		start = start - 1
		if store.get(start, None) is None:
			print('-1')
		else:
			print(store[start] + 1)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	s = input().strip()
	n = len(s)
	q = int(input())
	a = list(map(int, input().split()))
	cl = []
	b = [0] * n
	prev = n
	for i in range(n - 1, -1, -1):
		if s[i] == '(':
			prev = i
			if len(cl) == 0:
				b[i] = -1
			else:
				m = len(cl)
				b[i] = cl[m - 1]
				cl.pop()
		elif s[i] == ')':
			cl.append(i)
			b[i] = prev
	for i in range(0, q):
		m = a[i] - 1
		if s[m] == '(':
			if b[m] == -1:
				print(-1)
			else:
				print(b[m] + 1)
		elif s[m] == ')':
			tmp = b[m]
			if tmp == n:
				print(-1)
			elif b[tmp] == -1:
				print(-1)
			else:
				print(b[tmp] + 1)


t = int(input())
while t:
	s = input()
	q = int(input())
	a = list(map(int, input().strip().split()))[:q]
	ans = [-1] * len(s)
	stack = []
	for i in range(len(s) - 1, -1, -1):
		if s[i] == ')':
			stack.append(i + 1)
			if i != len(s) - 1:
				ans[i] = ans[i + 1]
		elif stack and s[i] == '(':
			l = stack.pop()
			ans[i] = l
		else:
			ans[i] = -1
	for i in a:
		print(ans[i - 1])
	t -= 1


def findbalance(string):
	n = len(string)
	default = -1
	main = []
	stk = []
	for i in range(n):
		if string[i] == ')':
			if stk:
				main.append(default)
				stk.append(i)
			else:
				main.append(default)
				stk.append(i)
		elif stk:
			default = n - stk.pop()
			main.append(default)
		else:
			default = -1
			main.append(default)
	return main[::-1]
for i in range(int(input())):
	string = input()
	Q = int(input())
	qlist = [int(i) for i in input().split()]
	reverse = string[::-1]
	d = [0] * 100
	main = findbalance(reverse)
	for j in qlist:
		print(main[j - 1])


def check(s):
	awin = len(s)
	chk = -1
	sol = []
	stack = []
	for i in range(awin):
		if s[i] == ')':
			if stack:
				sol.append(chk)
				stack.append(i)
			else:
				sol.append(chk)
				stack.append(i)
		elif stack:
			chk = awin - stack.pop()
			sol.append(chk)
		else:
			chk = -1
			sol.append(chk)
	return sol[::-1]
for i in range(int(input())):
	s = input()
	q = int(input())
	query = [int(i) for i in input().split()]
	demo = s[::-1]
	sol = check(demo)
	for i in query:
		print(sol[i - 1])