Bessie 有一个长度为 $N$ ($1\le N\le 3\cdot 10^5$) 的字符串，仅由字符 M 和 O 组成。对于字符串的每个位置 $i$，将其字符更改为另一个字符的代价为 $c_i$ ($1\le c_i\le 10^8$)。Bessie 认为如果字符串包含更多长度为 $L$ ($1\le L\le \min(N, 3)$) 的“moo”，它看起来会更好。长度为 $L$ 的“moo”是指一个 M 后跟 $L-1$ 个 O。对于从 $1$ 到 $\lfloor N/L\rfloor$ 的每个正整数 $k$，计算将字符串更改为至少包含 $k$ 个长度为 $L$ 的“moo”子串所需的最小代价。

输入格式

第一行包含两个整数 $L$ 和 $N$。 第二行包含 Bessie 的长度为 $N$ 的字符串，仅由 M 和 O 组成。 第三行包含空格分隔的整数 $c_1\dots c_N$。

输出格式

输出 $\lfloor N/L\rfloor$ 行，按递增顺序输出每个 $k$ 的答案。

样例

样例输入 1

1 4
MOOO
10 20 30 40

样例输出 1

0
20
50
90

样例输入 2

3 4
OOOO
50 40 30 20

样例输出 2

40

样例输入 3

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

样例输出 3

0
0
0
0
0
12851185
35521020
60232254
99881782
952304708

样例输入 4

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

样例输出 4

0
0
0
44743602
119332891
207066974

数据范围

• 输入 5: $L=3, N\le 5000$
• 输入 6: $L=1$
• 输入 7-10: $L=2$
• 输入 11-18: $L=3$