AT_agc074_e [AGC074E] Delete AB

For a string $ X = X_1X_2\dots X_{|X|} $ and positive integers $ l,r~(1 \leq l \leq r \leq |X|) $ , let $ X_{l,r} = X_l X_{l+1}\dots X_r $ . You are given a string $ S=S_1S_2\dots S_{|S|} $ consisting of `A` and `B`. You are given $ Q $ queries. For each query, answer the following question: - Starting from the state $ T = S_{l,r} $ , find the minimum possible length of a palindrome that can be obtained by performing the operation "choose one occurrence of `AB` that appears as a contiguous substring in $ T $ and delete it" zero or more times. If no palindrome can be obtained regardless of how the operation is performed, output `-1`.

The input is given from Standard Input in the following format: > $ S $ $ Q $ $ \mathrm{Query}_1 $ $ \mathrm{Query}_2 $ $ \vdots $ $ \mathrm{Query}_Q $ $ \mathrm{Query}_q $ represents the $ q $ -th query and is given in the following format: > $ l $ $ r $

Output $ Q $ lines. The $ q $ -th line should contain the answer for $ \mathrm{Query}_q $ .

### Sample Explanation 1 For the first, second, and third queries, by performing the operation as follows, you can obtain a palindrome with the minimum length among those obtained by the operation. - `ABBABB` $ \rightarrow $ `ABBB` $ \rightarrow $ `BB` - `AB` $ \rightarrow $ (empty string) - `BAB` $ \rightarrow $ `B` ### Constraints - $ 1 \leq |S| \leq 4 \times 10^5 $ - $ 1 \leq Q \leq 5 \times 10^4 $ - $ 1 \leq l \leq r \leq |S| $ - $ S $ is a string consisting of `A` and `B`. - $ Q,l,r $ are integers.