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: interview

Starter code:

Solutions:
import sys
import bisect as bi
import math
from collections import defaultdict as dd
input=sys.stdin.readline
##sys.setrecursionlimit(10**7)
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)#input wgera
    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   # corner case
    for i in range(n-2,-1,-1):
        if(s[i]=='('):    #dekhna h ki agla agr ( h toh -1 hi rhega wrna wo jo stored tha uppr
            if(store1[i]!=-1):post[i]=store1[i] #wo iska ans ho jayega
        else:post[i]=post[i+1]  #jo iske agle ka answer hoga wahi iska hoga
    for i in a:
        if(f):print(-1)  #cond ki jaroorat nhi thi pr tasalli (>_<)
        else:print(post[i-1]) #wrna uska ans print kra do
    
    
##n=m=0
##s=''
##t=''
##dp=[]
##def solve(inds,indt,k,cont):
##    ans=-999999999999999
##    print(dp)
##    if(k<0):return 0
##    elif(inds>=n and indt>=m):return 0
##    elif(dp[inds][indt][k][cont]!=-1):return dp[inds][indt][k][cont]
##    else:
##        if(indt<m):ans=max(ans,solve(inds,indt+1,k,0))
##        if(inds<n):ans=max(ans,solve(inds+1,indt,k,0))
##        if(s[inds]==t[indt]):
##            ans=max(ans,solve(inds+1,indt+1,k-1,1)+1)
##            if(cont):ans=max(ans,solve(inds+1,indt+1,k,1)+1)
##        dp[inds][indt][k][cont]=ans
##        return ans    

##    n,m,k=cin()
##    s=sin().strip()
##    t=sin().strip()
##    dp=[[[[-1]*2 for i in range(k)] for i in range(m+1)] for i in range(n+1)]
##    c=0
##    for i in dp:
##        for j in i:
##            for l in j:
##                c+=1
##                print(l,c)
##    print(solve(0,0,k,0))


# cook your dish here
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)


# cook your dish here
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 and stack[-1][0] == 1:
                _, pos = stack.pop()
                closing[i] = pos
            else:
                stack.append((0,i))
        else:
            stack.append((1,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)
#    q = int(input())
    n = len(s)
    answer=[]
    stack = []
    stack2 = []
    for i in range(len(s)-1,-1,-1):
#        print(stack)
#        print(s[i])
        if s[i]==')':
            if answer==[]:
                answer = [-1]
                stack2.append(i)
                stack.append(')')
                continue
            stack2.append(i)
            answer.append(answer[-1])
            stack.append(')')
        else:
            if stack2==[]:
                answer.append(-1)
                stack.append('(')
            else:
                stack.pop()
                e = stack2[-1]
                stack2.pop()
                answer.append(e+1)
#        if i==5:
#            break
    answer.reverse()
    q = int(input())
    W = list(map(int,input().split()))
    for i in range(q):
        w = W[i]
        print(answer[w-1])
#    print(answer)
                
        
        


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
		else:
			if 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
	# lastClose=-1
	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]
			# lastClose=i+1
			tracker-=1
		elif tracker<0 and st[i]=='(':
			ans[i]=stack.pop()
			tracker+=1
	# print(ans)
	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

# cook your dish here
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):
        #print(string[j])
        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]
    #print(l)    
    for item in a:
        print(l[item])
        


# cook your dish here
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):
        #print(string[j])
        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]
    #print(l)    
    for item in a:
        print(l[item])
        


# cook your dish here
from sys import stdin, stdout  
  

def main(): 
  
    t = input() 
    t=int(t)
    while t:
        t=t-1
        s=input()
        n=len(s)
        #print(n,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())
        #print(l)
        
        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)
            
        
            
        
  
        
  
 
    
  
# call the main method 
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
        else:
            if 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])
        
    


# from mymodule import input
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)
    # for i in tmp:
    #     li[i] = len(s)
    # print(li,stk)
    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
                
        else:
            if len(stk) == 0:
                store[i] = -1
                last = -1
            else:
                x = stk.pop()
                store[i] = x
                last = x
                
    # print(store)
            
    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")

# sys.stdout=open("CP3/output.txt",'w')
# sys.stdin=open("CP3/input.txt",'r')

# m=pow(10,9)+7
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]==')':
            # c1-=1
            # if c1>=0:
            #     c=0
            v[j]=prev
            st.append(j)
        else:
            c1+=1
            c+=1
            if st:
                v[j]=st.pop()
            else:
                v[j]=-2
            prev=v[j]
            # if len(st)>=c:
            #     v[j]=st[-c]
            #     prev=st[-c]
            # else:
            #     v[j]=-2
            #     prev=-2
    q1=int(input())
    q=list(map(int,input().split()))
    # print(v)
    for j in q:
        print(v[j-1]+1)