E - Delete AB Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MiB

配点 : 1200 点

問題文

文字列 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 を出力してください。

制約

  • 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 は整数

入力

入力は以下の形式で標準入力から与えられる。

S
Q
\mathrm{Query}_1
\mathrm{Query}_2
\vdots
\mathrm{Query}_Q

\mathrm{Query}_q は q 個目のクエリを表し、以下の形式で与えられる。

l r

出力

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

入力例 1

ABBABB
5
1 6
4 5
3 5
2 3
3 4

出力例 1

2
0
1
2
-1

1 個目、2 個目、3 個目のクエリについて、以下のように操作を行うことで、操作によって得られる回文のうち長さが最小のものが得られます。

  • ABBABB \rightarrow ABBB \rightarrow BB
  • AB \rightarrow (空文字列)
  • BAB \rightarrow B

Score : 1200 points

Problem Statement

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.

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.

Input

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

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

Sample Input 1

ABBABB
5
1 6
4 5
3 5
2 3
3 4

Sample Output 1

2
0
1
2
-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