仅由括号 '(' 和 ')' 组成的字符串，如果满足以下条件之一，则称为平衡的：

• 字符串 "()" 是平衡的。
• 两个平衡字符串的连接是平衡的。
• 当字符串 $s$ 是平衡的时，按顺序连接字符串 "(", $s$, 和 ")" 得到的字符串也是平衡的。

注意，该条件比单纯要求 '(' 和 ')' 的数量相等要严格。例如，"())(()" 不是平衡的。

你的任务是在宇宙射线可能翻转括号方向的严苛条件下，保持字符串处于平衡状态。

初始时给定一个平衡字符串。每次单个括号的方向被翻转时，程序会收到该字符在字符串中的位置。你需要计算并输出最左侧的位置，使得如果翻转该位置的括号，整个字符串能恢复到平衡状态。在你的程序指出需要翻转的括号并使字符串恢复平衡后，下一次宇宙射线会翻转另一个括号，上述步骤会重复多次。

输入格式

输入包含单个测试用例，格式如下：

$N \ Q$ $s$ $q_1$ $\vdots$ $q_Q$

第一行包含两个整数 $N$ 和 $Q$ ($2 \le N \le 300000, 1 \le Q \le 150000$)。第二行是一个长度为 $N$ 的平衡括号字符串 $s$。接下来的 $Q$ 行，每行包含一个整数 $q_i$ ($1 \le q_i \le N$)，表示第 $q_i$ 个括号的方向被翻转。

输出格式

对于每次事件 $q_i$，输出为了使字符串恢复平衡，你需要翻转的最左侧括号的位置。

注意，每次输入翻转事件 $q_i$ 都是在之前的翻转 $q_{i-1}$ 及其修复操作之后，在当前字符串状态上进行的。

样例

样例输入 1

6 3
((()))
4
3
1

样例输出 1

2
2
1

样例输入 2

20 9
()((((()))))()()()()
15
20
13
5
3
10
3
17
18

样例输出 2

2
20
8
5
3
2
2
3
18

说明

在第一个样例中，初始状态为 "((()))"。第 4 个括号被翻转，字符串变为 "(((())"。为了保持平衡，你应该翻转第 2 个括号，得到 "()(())"。下一次翻转第 3 个括号是在上一个状态的基础上进行的，得到 "())())"。为了重新平衡，你必须再次改变第 2 个括号，得到 "(()())"。