Time Limit: 2 sec / Memory Limit: 1024 MB

Score : `100` points

### Problem Statement

You have a string `s=s_0s_1...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.

- Step: For all substrings of
`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`.

### 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.

### Input

Input is given from Standard Input in the following format:

NsQl_1r_1l_2r_2:l_Qr_Q

### Output

After each query, print the value of `f(``B`

`+` `s` `+` `A`

`)`, one per line.

### Sample Input 1

5 BAABA 2 1 3 0 2

### Sample Output 1

6 6

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.

### Sample Input 2

1 A 2 0 0 0 0

### Sample Output 2

2 2