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, i^th query is of form x_i, , 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, x_i.

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