Mammali's Way Out - Repovive Starter Round 6 | Repovive

19E. Mammali's Way Out

2500 pts1s256 MB

You are given an array $a$ of length $n$ , indexed from $1$ to $n$ . Every element of the array is either $+1$ or $-1$ . The array is represented by a string $s$ , where $s_i$ is + if $a_i=+1$ , and - if $a_i=-1$ .

An experiment can start at any position $i$ . Before every experiment, the array is restored to its initial state.

In the $i$ -th experiment, Mammali starts at position $i$ . While he is inside the array, suppose that his current position is $p$ and let $x=a_p$ . He performs the following actions:

he moves to position $p+x$ ;
$a_p$ is replaced by $-a_p$ , where $p$ is the position he just left.

In other words, the move uses the value of the position before its sign is reversed.

If Mammali reaches position $0$ , he exits from the left. If he reaches position $n+1$ , he exits from the right.

You are given $q$ queries. In the $j$ -th query, Mammali separately performs one experiment from every starting position $i$ such that $l_j \le i \le r_j$ . Determine how many of these experiments end with Mammali exiting from the left.

Queries do not change the array, and every experiment is independent of all other experiments.

Constraints

$1 \le n,q \le 2 \times 10^5$
$|s|=n$
$s_i$ is either + or -
$1 \le l_i \le r_i \le n$

Input

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

The second line contains the string $s$ .

Each of the next $q$ lines contains two integers $l_i$ and $r_i$ , describing a query.

Output

For each query, output one integer: the number of starting positions in its range from which Mammali exits from the left.

Samples

Input

Explanation

Starting from position $1$ , the states after successive moves are:

position $2$ , string “---+”;
position $1$ , string “-+-+”;
position $0$ , string “++-+”.

Thus, Mammali exits from the left.

Starting from position $3$ , the states after successive moves are:

position $2$ , string “+-++”;
position $1$ , string “++++”;
position $2$ , string “-+++”;
position $3$ , string “--++”;
position $4$ , string “---+”;
position $5$ , string “----”.

Thus, Mammali exits from the right. The other two experiments can be followed in the same way.

In fact, starts $1$ and $2$ exit left, while starts $3$ and $4$ exit right. Therefore, the four query answers are $2$ , $2$ , $0$ , and $1$ .

Output

Input

5 3
-++--
1 5
2 4
4 5

Explanation

Starting from position $2$ , the states after successive moves are:

position $3$ , string “--+--”;
position $4$ , string “-----”;
position $3$ , string “---+-”;
position $2$ , string “--++-”;
position $1$ , string “-+++-”;
position $0$ , string “++++-”.

Thus, Mammali exits from the left.

Starting from position $5$ , the states after successive moves are:

position $4$ , string “-++-+”;
position $3$ , string “-++++”;
position $4$ , string “-+-++”;
position $5$ , string “-+--+”;
position $6$ , string “-+---”.

Thus, Mammali exits from the right. The other experiments can be followed in the same way.

The experiments starting at positions $1$ , $2$ , and $3$ exit left. The experiments starting at positions $4$ and $5$ exit right. Hence, all five positions contain three left exits, positions $2$ through $4$ contain two, and positions $4$ through $5$ contain none.

Output

3
2
0

An experiment can start at any position $i$ . Before every experiment, the array is restored to its initial state.

In the $i$ -th experiment, Mammali starts at position $i$ . While he is inside the array, suppose that his current position is $p$ and let $x=a_p$ . He performs the following actions:

he moves to position $p+x$ ;
$a_p$ is replaced by $-a_p$ , where $p$ is the position he just left.

In other words, the move uses the value of the position before its sign is reversed.

If Mammali reaches position $0$ , he exits from the left. If he reaches position $n+1$ , he exits from the right.

Queries do not change the array, and every experiment is independent of all other experiments.

$1 \le n,q \le 2 \times 10^5$
$|s|=n$
$s_i$ is either + or -
$1 \le l_i \le r_i \le n$

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

The second line contains the string $s$ .

Each of the next $q$ lines contains two integers $l_i$ and $r_i$ , describing a query.

Starting from position $1$ , the states after successive moves are:

position $2$ , string “---+”;
position $1$ , string “-+-+”;
position $0$ , string “++-+”.

Thus, Mammali exits from the left.

Starting from position $3$ , the states after successive moves are:

position $2$ , string “+-++”;
position $1$ , string “++++”;
position $2$ , string “-+++”;
position $3$ , string “--++”;
position $4$ , string “---+”;
position $5$ , string “----”.

Thus, Mammali exits from the right. The other two experiments can be followed in the same way.

In fact, starts $1$ and $2$ exit left, while starts $3$ and $4$ exit right. Therefore, the four query answers are $2$ , $2$ , $0$ , and $1$ .

Starting from position $2$ , the states after successive moves are:

position $3$ , string “--+--”;
position $4$ , string “-----”;
position $3$ , string “---+-”;
position $2$ , string “--++-”;
position $1$ , string “-+++-”;
position $0$ , string “++++-”.

Thus, Mammali exits from the left.

Starting from position $5$ , the states after successive moves are:

position $4$ , string “-++-+”;
position $3$ , string “-++++”;
position $4$ , string “-+-++”;
position $5$ , string “-+--+”;
position $6$ , string “-+---”.

Thus, Mammali exits from the right. The other experiments can be followed in the same way.

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

19E. Mammali's Way Out

Constraints

Input

Output

Samples

19E. Mammali's Way Out

Constraints

Input

Output

Samples