P8793 [Lanqiao Cup 2022 National A] owo

Unlike the Lanqiao Cup judge testdata, this problem assumes that each character is either `o` or `w`, to avoid meaningless and more complicated case discussions (the original problem also did not clearly state the constraints).

Xiao Lan likes `owo` very much. He now has some strings, and he wants to concatenate these strings so that the final string contains as many `owo` as possible. When counting, overlapping is allowed. For example, `owowo` is counted as $2$, and `owowowo` is counted as $3$. Please compute how many `owo` can appear in the final string under the best strategy.

The first line contains an integer $n$, which indicates the number of strings Xiao Lan has. The next $n$ lines each contain a string $s_i$ consisting of lowercase English letters.

Output $n$ lines, each containing an integer, which represents the maximum number of `owo` that can be obtained by optimally concatenating the first $i$ strings.

**[Test Case Scale and Assumptions]** - For $10\%$ of the test cases, $n \leq 10$. - For $40\%$ of the test cases, $n \leq 300$. - For $60\%$ of the test cases, $n \leq 5000$. - For all test cases, $1 \leq n \leq 10^6$, $1 \leq |s_i|,\sum|s_i| \leq 10^6$, where $|s_i|$ denotes the length of string $s_i$. Each character is either $\tt o$ or $\tt w$. Lanqiao Cup 2022 National Contest, Group A, Problem E. Translated by ChatGPT 5