Moo Substring Transformation

Bessie has a string of length \(N\) (where \(1 \le N \le 3\cdot10^5\)) consisting solely of the characters M and O. For each position \(i\) in the string, changing the character to the other letter costs \(c_i\) (\(1 \le c_i \le 10^8\)).

Bessie thinks the string will look better if it contains more moos of length \(L\) (with \(1 \le L \le \min(N,3)\)). A moo of length \(L\) is defined as an occurrence of a substring that is exactly \(M\) followed by \(L-1\) copies of \(O\) (i.e. the pattern \(M\,O\,\cdots\,O\)).

You are given an integer \(L\) together with the string and the cost array. For every positive integer \(k\) from \(1\) to \(\lfloor N/L\rfloor\), compute the minimum total cost needed to change characters in the string so that it contains at least \(k\) (non‐overlapping) substrings equal to the moo pattern (i.e. the substring equals \(M\,\underbrace{O\cdots O}_{L-1}\)).

Note: The time limit for this problem is 3 seconds (usually 1.5 times the normal limit).

inputFormat

The first line contains two integers \(N\) and \(L\) (with \(1 \le L \le \min(N,3)\)).

The second line contains a string of length \(N\) containing only the characters M and O.

The third line contains \(N\) space‐separated integers \(c_1, c_2, \dots, c_N\) representing the cost to change the character at position \(i\) to the other character.

outputFormat

Output \(\lfloor N/L\rfloor\) lines. The \(k\)th line (for \(1 \le k \le \lfloor N/L\rfloor\)) should contain a single integer: the minimum total cost to modify the string so that it contains at least \(k\) non‐overlapping moo substrings of length \(L\).

sample

5 1
MOMOM
1 1 1 1 1

0
0
0
1
2