Bessie has a string of length N (1≤N≤3⋅10^5) consisting solely of the characters M and O. For each position i of the string, there is a cost c_i to change the character at that position to the other character (1≤c_i≤10^8).

Bessie thinks the string will look better if it contains more moos of length L (1≤L≤min(N,3)). A moo of length L is an M followed by L−1 Os.

For each positive integer k from 1 to ⌊N/L⌋ inclusive, compute the minimum cost to change the string to contain at least k substrings equal to a moo of length L.

#8189 upload -회 done -회 how_to_reg -명 call_split 서브태스크

It's Mooin' Time timer 3초 memory 1024MB

#8189
서브태스크

It's Mooin' Time 3초 1024MB