AT_agc074_e [AGC074E] Delete AB

对于一个字符串 $X = X_1X_2\dots X_{|X|}$ 和正整数 $l, r~(1 \leq l \leq r \leq |X|)$，记 $X_{l,r} = X_l X_{l+1}\dots X_r$。 给定一个仅由 `A` 和 `B` 组成的字符串 $S = S_1S_2\dots S_{|S|}$。 你需要回答 $Q$ 个查询。对于每个查询，回答如下问题： - 从状态 $T = S_{l,r}$ 开始，可以进行多次如下操作：“选择 $T$ 中出现的一处连续的 `AB` 并将其删除”。最终可以得到若干不同的字符串。 问通过若干步操作后，能够得到的回文字符串的最小可能长度是多少？如果无论如何操作都无法得到回文字符串，输出 $-1$。

输入从标准输入读入，格式如下： > $S$ > $Q$ > $\mathrm{Query}_1$ > $\mathrm{Query}_2$ > $\vdots$ > $\mathrm{Query}_Q$ 其中 $\mathrm{Query}_q$ 表示第 $q$ 个查询，格式如下： > $l \ r$

输出共 $Q$ 行，第 $q$ 行输出对于 $\mathrm{Query}_q$ 的答案。

### 样例解释 1 对于第 1、2、3 个查询，进行如下操作可以得到最小长度的回文串： - `ABBABB` $\rightarrow$ `ABBB` $\rightarrow$ `BB` - `AB` $\rightarrow$ （空字符串） - `BAB` $\rightarrow$ `B` ### 数据范围 - $1 \leq |S| \leq 4 \times 10^5$ - $1 \leq Q \leq 5 \times 10^4$ - $1 \leq l \leq r \leq |S|$ - $S$ 是只包含字母 `A` 和 `B` 的字符串。 - $Q, l, r$ 均为整数。 由 ChatGPT 5 翻译