Problem Statement

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 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.

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.

Input

The input is given from Standard Input in the following format:

N K
S

Output

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