{"problem":{"name":"Delete AB","description":{"content":"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` an","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc074_e"},"statements":[{"statement_type":"Markdown","content":"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$.\nYou are given a string $S=S_1S_2\\dots S_{|S|}$ consisting of `A` and `B`.  \nYou are given $Q$ queries. For each query, answer the following question:\n\n*   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.  \n    If no palindrome can be obtained regardless of how the operation is performed, output `-1`.\n\n## Constraints\n\n*   $1 \\leq |S| \\leq 4 \\times 10^5$\n*   $1 \\leq Q \\leq 5 \\times 10^4$\n*   $1 \\leq l \\leq r \\leq |S|$\n*   $S$ is a string consisting of `A` and `B`.\n*   $Q,l,r$ are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$S$\n$Q$\n$\\mathrm{Query}_1$\n$\\mathrm{Query}_2$\n$\\vdots$\n$\\mathrm{Query}_Q$\n\n$\\mathrm{Query}_q$ represents the $q$\\-th query and is given in the following format:\n\n$l$ $r$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc074_e","tags":[],"sample_group":[["ABBABB\n5\n1 6\n4 5\n3 5\n2 3\n3 4","2\n0\n1\n2\n-1\n\nFor 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.\n\n*   `ABBABB` $\\rightarrow$ `ABBB` $\\rightarrow$ `BB`\n*   `AB` $\\rightarrow$ (empty string)\n*   `BAB` $\\rightarrow$ `B`"]],"created_at":"2026-03-03 11:01:13"}}