Longest Valid Parentheses Substring from Constructed Sequence

DerrickLo has two sequences: a positive integer sequence ({a_i}{i=1}^n) and a bracket sequence ({t_i}{i=1}^n) where each (t_i) is either '(' or ')'. He will answer (q) queries. For each query he selects two indices (l) and (r) (with (1 \le l \le r \le n)) to construct a new string (S) as follows:

For each (i) from (l) to (r) (in increasing order), append (a_i) copies of the character (t_i) to (S).

Your task is to compute the length of the longest contiguous substring of (S) that is a valid parentheses sequence.

A string is said to be a valid parentheses sequence if it meets the following criteria:

\begin{enumerate} \item The empty string is valid. \item If (A) is a valid sequence, then ((A)) is valid. \item If both (A) and (B) are valid sequences, then their concatenation (AB) is valid. \end{enumerate}

inputFormat

The first line contains two integers (n) and (q) ((1 \le n, q \le 10^5)) -- the length of the sequences and the number of queries.\n\nThe second line contains (n) positive integers (a_1, a_2, \dots, a_n).\n\nThe third line contains a string of length (n), consisting only of the characters '(' and ')', representing (t_1, t_2, \dots, t_n).\n\nEach of the following (q) lines contains two integers (l) and (r) ((1 \le l \le r \le n)), representing a query.

outputFormat

For each query, output a single integer on a new line -- the length of the longest valid parentheses substring in the constructed string (S).

sample

3 1
1 1 1
(()
1 3

2