AT_agc072_b [AGC072B] AGC Language

An AGC word is a string of length at least $ 2 $ that contains the same number of `A`’s and `C`’s, and in every prefix, `A`’s make up at least half of the characters. You are given a string $ S $ of length $ 2N $ consisting of $ N $ `A`’s and $ N $ `C`’s. For each $ k = 1, 2, \dots, K $ , answer the following question. > A blackboard shows a string that is a concatenation of $ k $ copies of $ S $ . To turn it into an AGC word, perform the operations below in the order written: > > 1. Perform **exactly once**: > - Choose integers $ (l, r) $ $ (1 \le l \le r \le 2kN) $ and reverse the $ l $ -th through $ r $ -th characters of the string. > 2. Perform **zero or more times**: > - Swap two adjacent characters of the string. > > What is the minimum number of swaps required? Notes on prefixA string $ Y $ is a prefix of $ X $ if and only if $ 1 \le |Y| \le |X| $ and the first $ |Y| $ characters of $ X $ equal $ Y $ . For example, `ATC` is a prefix of `ATCODER`, but `AGC` and `ATCODERGRANDCONTEST` are not.

The input is given from Standard Input in the following format: > $ N $ $ K $ $ S $

Print $ K $ lines. The $ i $ ‑th line $ (1 \le i \le K) $ should contain the answer for $ k = i $ .

### Sample Explanation 1 For $ k = 1 $ , the initial string is `AC`; For $ k = 2 $ , it is `ACAC`. Both are already AGC words, so choosing, say, $ (l, r) = (1, 1) $ yields $ 0 $ swaps. ### Sample Explanation 2 For $ k = 1 $ , the string is `CACAAACCCA`. By following the steps below, the sequence needs only one swap: 1. Choose $ (l, r) = (1, 4) $ and reverse the $ 1 $ -st through $ 4 $ -th characters. The string is now `ACACAACCCA`. 2. Swap the $ 9 $ -th and $ 10 $ -th characters. The string is now `ACACAACCAC`, which is an AGC word. ### Constraints - $ 1 \le N \le 1\,000\,000 $ - $ 1 \le K \le 300\,000 $ - $ S $ is a length‑ $ 2N $ string consisting of $ N $ `A`’s and $ N $ `C`’s. - $ N $ and $ K $ are integers.