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 $ つ選び削除する」という操作を $ 0 $ 回以上行うことによって得られる回文としてあり得る長さの最小値を求めてください。 どのように操作を行っても回文が得られない場合は `-1` を出力してください。

入力は以下の形式で標準入力から与えられる。 > $ S $ $ Q $ $ \mathrm{Query}_1 $ $ \mathrm{Query}_2 $ $ \vdots $ $ \mathrm{Query}_Q $ $ \mathrm{Query}_q $ は $ q $ 個目のクエリを表し、以下の形式で与えられる。 > $ l $ $ r $

$ Q $ 行出力せよ。 $ q $ 行目に $ \mathrm{Query}_q $ に対する答えを出力せよ。

### Sample Explanation 1 $ 1 $ 個目、 $ 2 $ 個目、 $ 3 $ 個目のクエリについて、以下のように操作を行うことで、操作によって得られる回文のうち長さが最小のものが得られます。 - `ABBABB` $ \rightarrow $ `ABBB` $ \rightarrow $ `BB` - `AB` $ \rightarrow $ (空文字列) - `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 $ は `A`, `B` からなる文字列 - $ Q,l,r $ は整数