{"problem":{"name":"AGC Language","description":{"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 lengt","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc072_b"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $K$\n$S$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc072_b","tags":[],"sample_group":[["1 2\nAC","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."],["5 1\nCACAAACCCA","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."],["10 10\nACCCAAAACCCACCACAACA","1\n2\n3\n3\n3\n3\n3\n3\n3\n3"],["50 10\nACCCCACAACAAAACCAACCCCACCAACACCAAAACACACAAAACCCCCACCAACACAACAACCCCAACAAACCCAACACACCCACACCAAACCCAAACA","10\n17\n20\n22\n23\n24\n25\n26\n26\n26"],["72 10\nCCCCACAAAAACCCACACCAAACCACCCCCAAAAACACCACCCCCAAAAAAACAAAAAACCCCCCACCCAAACAACACCACCACAAACCCAACCAACAACCCAAAACAACCCCACCACACACCACACCCACAAACACAACAACA","28\n42\n51\n54\n57\n60\n63\n64\n65\n66"]],"created_at":"2026-03-03 11:01:13"}}