{"raw_statement":[{"iden":"problem statement","content":"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.\n\n> 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:\n> \n> 1.  Perform **exactly once**:\n>     *   Choose integers $(l, r)$ $(1 \\le l \\le r \\le 2kN)$ and reverse the $l$\\-th through $r$\\-th characters of the string.\n> 2.  Perform **zero or more times**:\n>     *   Swap two adjacent characters of the string.\n> \n> What is the minimum number of swaps required?\n\nNotes on prefix A 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."},{"iden":"constraints","content":"*   $1 \\le N \\le 1\\,000\\,000$\n*   $1 \\le K \\le 300\\,000$\n*   $S$ is a length‑$2N$ string consisting of $N$ `A`’s and $N$ `C`’s.\n*   $N$ and $K$ are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $K$\n$S$"},{"iden":"sample input 1","content":"1 2\nAC"},{"iden":"sample output 1","content":"0\n0\n\nFor $k = 1$, the initial string is `AC`;  \nFor $k = 2$, it is `ACAC`.\nBoth are already AGC words, so choosing, say, $(l, r) = (1, 1)$ yields $0$ swaps."},{"iden":"sample input 2","content":"5 1\nCACAAACCCA"},{"iden":"sample output 2","content":"1\n\nFor $k = 1$, the string is `CACAAACCCA`. By following the steps below, the sequence needs only one swap:\n\n1.  Choose $(l, r) = (1, 4)$ and reverse the $1$\\-st through $4$\\-th characters. The string is now `ACACAACCCA`.\n2.  Swap the $9$\\-th and $10$\\-th characters. The string is now `ACACAACCAC`, which is an AGC word."},{"iden":"sample input 3","content":"10 10\nACCCAAAACCCACCACAACA"},{"iden":"sample output 3","content":"1\n2\n3\n3\n3\n3\n3\n3\n3\n3"},{"iden":"sample input 4","content":"50 10\nACCCCACAACAAAACCAACCCCACCAACACCAAAACACACAAAACCCCCACCAACACAACAACCCCAACAAACCCAACACACCCACACCAAACCCAAACA"},{"iden":"sample output 4","content":"10\n17\n20\n22\n23\n24\n25\n26\n26\n26"},{"iden":"sample input 5","content":"72 10\nCCCCACAAAAACCCACACCAAACCACCCCCAAAAACACCACCCCCAAAAAAACAAAAAACCCCCCACCCAAACAACACCACCACAAACCCAACCAACAACCCAAAACAACCCCACCACACACCACACCCACAAACACAACAACA"},{"iden":"sample output 5","content":"28\n42\n51\n54\n57\n60\n63\n64\n65\n66"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}