Problem Description

You have a string \( s = s_0 s_1 \ldots s_{N-1} \) of length \( N \) consisting of A and B. You have to process \( Q \) queries. Consider the \( i \)-th query ( \( 1 \leq i \leq Q \) ). In this query you are given integers \( l_i \) and \( r_i \). Then, for each \( x \) ( \( l_i \leq x \leq r_i \) ), \( s_x \) is changed to the other letter, that is, A becomes B and B becomes A.

After each query, you have to calculate \( f(\) B \( + \) \( s \) \( + \) A \() \). Here, \( f(t) \) is a function which, given a string \( t \), returns a non-negative integer. The value of \( f(t) \) is defined as follows:

• Consider the following step.
• Step: For all substrings of \( t \) which coincide with BA, replace them with AB. All replacements are done at the same time.
• \( f(t) \) is the number of steps you need to perform until no substring of \( t \) coincides with BA.

For example, \( f(\) ABAB \() = 1 \), \( f(\) BBAA \() = 3 \), and \( f(\) AAA \() = 0 \).

Input Format

Input is given from Standard Input in the following format:

\( N \) \( s \) \( Q \) \( l_1 \) \( r_1 \) \( l_2 \) \( r_2 \) : \( l_Q \) \( r_Q \)

Output Format

After each query, print the value of \( f(\) B \( + \) \( s \) \( + \) A \() \), one per line.

Sample Input and Output

Sample Input #1

5
BAABA
2
1 3
0 2

Sample Output #1

6
6

Sample Input #2

1
A
2
0 0
0 0

Sample Output #2

2
2

Notes/Hints

Constraints

• \( 1 \leq N \leq 200000 \)
• \( |s| = N \)
• \( s \) consists of A and B.
• \( 1 \leq Q \leq 200000 \)
• \( 0 \leq l_i \leq r_i \leq N-1 \)
• \( N, Q, l_i, r_i \) are integers.

Sample Explanation 1

After the first query, the string \( s \) is BBBAA, so print the value of \( f(\) BBBBAAA \() \) in the first line. After the second query, the string \( s \) is AAAAA, so print the value of \( f(\) BAAAAAA \() \) in the second line.

见题面 Input 部分

见题面 Output 部分