Background

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).

Problem Description

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.

Input Format

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 Format

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.

3
owo
w
ow

1
1
2

Hint

[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