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$.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = "from collections import deque \nfrom sys import stdin\ninput=stdin.readline\nfor _ in range(int(input())):\n    s=list(input())\n    n=len(s)\n    ans=[0]*n\n    x=0\n    y=0\n    a=n-1\n    b=n-1\n    stack=deque([])\n    prev=-1\n    while a>=0:\n        if s[a]==')':\n            stack.append(a)\n            ans[a] = prev\n        else:\n            if len(stack)==0:\n                ans[a]=-1\n                prev=-1\n            else:\n                prev=stack[-1]+1\n                ans[a]=prev\n                stack.pop()\n        a-=1\n    \n    q=int(input())\n    x=list(map(int,input().split()))\n    for i in x:\n        i=i-1\n        print(ans[i])\n        \n    \n"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13991