Matching
Time limit: 5 seconds
Problem
A lot of text editors have an auto-match ability.
When you highlight an opening or
closing parenthesis, i.e., '(' or ')',
the matching parenthesis will be highlighted automatically.
This problem requires you to do something similar.
Input
The input consists of a number of test cases.
For each test case, the first line contains
two integers 1 <= n <= 1,000,000
and 1 <= m <= 1,000.
The next line is a list of n parentheses.
The parentheses are balanced.
Then there are m lines, each
containing a single integer q, which is a query asking
for the parenthesis that matches the q-th parenthesis
in the list.
The last test case starts with "0 0" and
no further lines. Do not process this case.
Output
For each query q, output an integer i on a single line
such that the i-th parenthesis matches
the q-th parenthesis.
Output a blank line after each test case.
Sample Input
20 5
((((((()()()()))))))
1
19
5
7
10
30 4
()()()()()((((((()()()()))))))
1
2
11
15
0 0
Sample Output
20
2
16
8
9
2
1
30
26
Author
Angela Siu