题目描述

给定一个长度为 $N$ 的字符串 $s=s_0s_1...s_{N-1}$，由字符 A 和 B 组成。你需要处理 $Q$ 个查询。考虑第 $i$ 个查询（$1 \leq i \leq Q$）。在这个查询中，给定整数 $l_i$ 和 $r_i$。然后，对于每个 $x$（$l_i \leq x \leq r_i$），$s_x$ 被修改为另一个字符，即 A 变为 B，B 变为 A。

在每个查询之后，你需要计算 $f($B $+$ $s$ $+$ A$)$。其中，$f(t)$ 是一个函数，给定一个字符串 $t$，返回一个非负整数。$f(t)$ 的值定义如下：

• 考虑以下 步骤。
  • 步骤：对所有与 BA 相同的子串，用 AB 替换它们。所有替换同时进行。
• $f(t)$ 是你需要执行的步骤数，直到 $t$ 中不存在与 BA 相同的子串为止。

例如，$f($ABAB$)$ \= $1$，$f($BBAA$)$ \= $3$，$f($AAA$)$ \= $0$。

约束条件

• $1 \leq N \leq 200000$
• $|s| = N$
• $s$ 由字符 A 和 B 组成。
• $1 \leq Q \leq 200000$
• $0 \leq l_i \leq r_i \leq N-1$
• $N,Q,l_i,r_i$ 均为整数

输入

输入从标准输入中给出，具体格式如下：

$N$ $s$ $Q$ $l_1$ $r_1$ $l_2$ $r_2$ ： $l_Q$ $r_Q$

输出

对于每个查询，每行输出 $f($B $+$ $s$ $+$ A$)$。

示例输入 1

5
BAABA
2
1 3
0 2

示例输出 1

6
6

第一个查询之后，字符串 $s$ 变为 BBBAA，在第一行打印 $f($BBBBAAA$)$。第二个查询之后，字符串 $s$ 变为 AAAAA，在第二行打印 $f($BAAAAAA$)$。

示例输入 2

1
A
2
0 0
0 0

示例输出 2

2
2