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 \leq t_i \leq N)$ and faces all characters from index $t_i$ to $N$. Find the minimum index $x$ $(t_i \leq x \leq 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 \leq T \leq 10^3$
- $1 \leq |S| \leq 10^7$
- $1 \leq Q \leq 10^6$
- $1 \leq t_i \leq 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
)())((()
3
1 7 6

-----Sample Output-----
3
8
-1

-----Explanation-----
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: UNKNOWN_DIFFICULTY

Starter code:

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

def cin():
	return list(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 list(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])


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)


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])


from sys import stdin, stdout

def main():
	t = input()
	t = int(t)
	while t:
		t = t - 1
		s = input()
		n = len(s)
		l = [0 for i in range(n)]
		l[n - 1] = -1
		q = []
		if s[n - 1] == ')':
			q.append(n - 1)
		for i in range(n - 2, -1, -1):
			if s[i] == ')':
				l[i] = l[i + 1]
				q.append(i)
			elif s[i] == '(' and len(q) == 0:
				l[i] = -1
			else:
				l[i] = q[len(q) - 1]
				q.pop()
		Q = int(input())
		arr = [int(x) for x in stdin.readline().split()]
		for i in range(Q):
			x = arr[i]
			x = x - 1
			if l[x] == -1:
				print(-1)
			else:
				print(l[x] + 1)

def __starting_point():
	main()
__starting_point()


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])


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)