AT_jag2018summer_day2_j AB Sort

[problemUrl]: https://atcoder.jp/contests/jag2018summer-day2/tasks/jag2018summer_day2_j 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. - $ 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 is given from Standard Input in the following format: > $ N $ $ s $ $ Q $ $ l_1 $ $ r_1 $ $ l_2 $ $ r_2 $ : $ l_Q $ $ r_Q $

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

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