BALANCE1PARA - Balance the parentheses

You are provided with a sequence of parentheses, that are balanced. A balanced parentheses sequence it that sequence in which every opening bracket has a unique closing bracket (nearest to it) to the right of it and every closing bracket has a unique opening bracket to the left of it (nearest). Any other sequence is not balanced. For example, (()), ()(), ((()())()), (), etc are balanced, but )(), ()), (()(, ()( are unbalanced.

You are then provided with q queries, ith query is of form xi, , representing an index. the bracket at that index is flipped that is, if it was an opening bracket then it is replaced by a closing one and vice versa. You have to give the left most index whose bracket has to be flipped so that the sequence remains balanced. The subsequent queries have to be applied on new sequence formed! 

Input

The first line will contain two integers, n and q. Next line will give you the sequence (n characters) consisting of opening and closing parenthesis only. Next q lines will represent q queries, xi.

Output

For each query, output the required answer in different lines.

Constraints

1<=n<=4*10^5

1<=q<=2*10^5

Example

Input:
10 10
()(((())))
2
7
9
4
5
1
4
3
5
4

Output:
2
4
6
4
2
1
2
2
4
4
Input:
6 9
((()))
6
2
2
6
4
6
3
2
4

Output:
6
2
2
6
2
6
2
2
3

Added by:Abhinandan Agarwal
Date:2016-08-17
Time limit:3.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU
Resource:ICPC-ASIA-TOKYO Regionals

hide comments
2016-08-31 17:09:13
what should be the time comlexity of the solution to be accepted?
2016-08-18 06:20:50
[Hidden]
RE: I tested the solution, with different approaches, i assure you that the unoptimised passes in one third time limit.

-- Thanks!

Last edit: 2016-08-19 01:08:55
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.