It's Mooin' Time

문제

Bessie has a string of length $NN$ ($1\le N\le 3\cdot {10}^{5}1\backslash le\; N\backslash le\; 3\backslash cdot\; 10^5$) consisting solely of the characters M and O. For each position $ii$ of the string, there is a cost $c_{i}c\_i$ to change the character at that position to the other character ($1\le c_i\le {10}^{8}1\backslash le\; c\_i\backslash le\; 10^8$).

Bessie thinks the string will look better if it contains more moos of length $LL$ ($1\le L\le \min (N,3)1\backslash le\; L\backslash le\; \backslash min(N,\; 3)$). A moo of length $LL$ is an M followed by $L-1L-1$ Os.

For each positive integer $kk$ from $11$ to $\lfloor N\mathrm{/}L\rfloor \backslash lfloor\; N/L\backslash rfloor$ inclusive, compute the minimum cost to change the string to contain at least $kk$ substrings equal to a moo of length $LL$.

입력

The first line contains $LL$ and $NN$.

The next line contains Bessie's length-$NN$ string, consisting solely of Ms and Os.

The next line contains space-separated integers $c_1\dots c_{N}c\_1\backslash dots\; c\_N$.

출력

Output $\lfloor N\mathrm{/}L\rfloor \backslash lfloor\; N/L\backslash rfloor$ lines, the answer for each $kk$ in increasing order.

1 4
MOOO
10 20 30 40

0
20
50
90

3 4
OOOO
50 40 30 20

40

2 20
OOOMOMOOOMOOOMMMOMOO
44743602 39649528 94028117 50811780 97338107 30426846 94909807 22669835 78498782 18004278 16633124 24711234 90542888 88490759 12851185 74589289 54413775 21184626 97688928 10497142

0
0
0
0
0
12851185
35521020
60232254
99881782
952304708

3 20
OOOMOMOOOMOOOMMMOMOO
44743602 39649528 94028117 50811780 97338107 30426846 94909807 22669835 78498782 18004278 16633124 24711234 90542888 88490759 12851185 74589289 54413775 21184626 97688928 10497142

0
0
0
44743602
119332891
207066974