题目描述

DerrickLo 有一个长度为 $n$ 的正整数序列 $a$，以及一个长度为 $n$ 的仅含有 ( 与 ) 的字符序列 $t$。他现在要根据这两个序列生成 $q$ 组括号序列，具体地，他会选择两个在 $[1,n]$ 中的正整数 $l,r$ 且 $l\le r$ 并对一个初始为空的字符串 $S$ 进行如下操作：

• 从小到大枚举每个在 $[l,r]$ 之间的正整数 $i$，将 $a_i$ 个 $t_i$ 加到 $S$ 的末尾。

他希望你能在每次他生成了一个括号序列 $S$ 后告诉他 $S$ 的最长合法匹配子串的大小。

合法匹配串的定义如下：

• 空串是合法匹配串。
• 若 $A$ 是合法匹配串，则 $(A)$ 为合法匹配串。
• 若 $A,B$ 都是合法匹配串，则 $AB$ 为合法匹配串。
• 除此以外的所有字符串都不是合法匹配串。

输入格式

第一行，两个正整数 $n,q$。

第二行，$n$ 个正整数表示 $a$。

第三行，一个字符串表示 $t$。

接下来 $q$ 行，每行两个正整数表示一次生成中的 $l,r$。

输出格式

$q$ 行，每行一个正整数表示答案。

3 2
2 3 1
()(
1 3
2 3

4
0

提示

样例说明

第一次生成的括号序列为 (()))(，它的最长合法匹配子串为 (())。

第二次生成的括号序列为 )))(，它的最长合法匹配子串为空串。

数据范围

$1\le n,q\le 10^6$，$1\le a_i\le 10^9$，每次生成中的 $l,r$ 满足 $1\le l\le r\le n$，$t$ 仅由 ( 与 ) 组成。除 $t$ 外所有输入数据为整数。