Description

DerrickLo has an integer array $a$ with $n$ numbers, and a array $t$ with $n$ characters which are either ( or ) ($1\le n\le 10^6$, $1\le a_i\le 10^9$). Now he will generate $q$ bracket strings by selecting an interval $[l,r]$ ($1\le l\le r\le n$) and perform the following operation to a string $S$ which is initially empty.

• For each integer $i$ from $l$ to $r$, append $a_i$ copies of $t_i$ to $S$.

After each generation, DerrickLo wants to know the longest good substring of $S$. Please help him!

A good string is defined as,

• An empty string is a good string.

• If $A$ is a good string, then so does $(A)$.

• If $A,B$ are both good strings, then so does $AB$.

• Any other strings are not good strings.

Input Format

The first line contains two integers $n,q$.

The second line contains $n$ integers representing $a$.

The third line contains a string representing $t$.

For the next $q$ lines, each one contains two integers representing $l,r$ for a generation.

Output Format

Output $q$ lines. The $i$-th one representing the $i$-th answer.

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

4
0

Hint

$S$ of the first generation is (()))(. Its longest good substring is (()), so output $4$.

$S$ of the second generation is )))(. Its longest good substring is an empty string, so output $0$.