Problem Statement

AGC字符串是一个至少长度为$2$，$A$字符和$C$字符数量相等，并且每一个前缀里面$A$的数量大于$C$的数量。

现在给你一个长度为$2N$的只含$N$个$A$,$N$个$C$的字符串，对于$k=1,2,...,K$,回答下面的问题。

我们把字符串复制$k$倍接起来，然后把它转换成为AGC字符串，我们可以进行如下操作：

• 有且必须一次操作

  • 选择 $(l, r)$ $(1 \le l \le r \le 2kN)$ 区间，并且把区间内的字符串翻转。

• 0次或者任意次操作

  • 交换相邻字符。

What is the minimum number of swaps required?

问最小的交换次数

输入

N K
S

输出

打印 $K$ 行。第 $i$ 行 $(1 \le i \le K)$ 应包含 $k = i$ 的答案。

Sample Input 1

1 2
AC

Sample Output 1

0
0

对于 $k = 1$ ，初始字符串是 AC； 对于 $k = 2$ , 它是 ACAC。

这两个词都已经是 AGC 词，因此选择 $(l, r) = (1, 1)$ 会产生 $0$ 的交换。

Sample Input 2

5 1
CACAAACCCA

Sample Output 2

1

对于 $k = 1$ ，字符串是 CACAAACCCA。按照下面的步骤，序列只需交换一次：

1. 选择 $(l, r) = (1, 4)$ 并翻转 $1$ -st 到 $4$ -th 字符。现在的字符串是 ACACAACCCA。
2. 交换 $9$ -th 和 $10$ -th 字符。字符串现在是 ACACAACCAC, 这是一个 AGC 字。

Sample Input 3

10 10
ACCCAAAACCCACCACAACA

Sample Output 3

1
2
3
3
3
3
3
3
3
3

Sample Input 4

50 10
ACCCCACAACAAAACCAACCCCACCAACACCAAAACACACAAAACCCCCACCAACACAACAACCCCAACAAACCCAACACACCCACACCAAACCCAAACA

Sample Output 4

10
17
20
22
23
24
25
26
26
26

Sample Input 5

72 10
CCCCACAAAAACCCACACCAAACCACCCCCAAAAACACCACCCCCAAAAAAACAAAAAACCCCCCACCCAAACAACACCACCACAAACCCAACCAACAACCCAAAACAACCCCACCACACACCACACCCACAAACACAACAACA

Sample Output 5

28
42
51
54
57
60
63
64
65
66