题目描述

小蓝很喜欢 owo，他现在有一些字符串，他想将这些字符串拼接起来，使得最终得到的字符串中出现尽可能多的 owo。

在计算数量时，允许字符重叠，即 owowo 计算为 $2$ 个，owowowo 计算为 $3$ 个。请算出最优情况下得到的字符串中有多少个 owo。

输入格式

输入的第一行包含一个整数 $n$，表示小蓝拥有的字符串的数量。

接下来 $n$ 行，每行包含一个由小写英文字母组成的字符串 $s_i$。

输出格式

输出 $n$ 行，每行包含一个整数，表示前 $i$ 个字符串在最优拼接方案中可以得到的 owo 的数量。

3
owo
w
ow

1
1
2

提示

【评测用例规模与约定】

• 对于 $10\%$ 的评测用例，$n \leq 10$；
• 对于 $40\%$ 的评测用例，$n \leq 300$；
• 对于 $60\%$ 的评测用例，$n \leq 5000$；
• 对于所有评测用例，$1 \leq n \leq 10^6$，$1 \leq |s_i|,\sum|s_i| \leq 10^6$，其中 $|s_i|$ 表示字符串 $s_i$ 的长度。字符不是 $\tt o$ 就是 $\tt w$。

蓝桥杯 2022 国赛 A 组 E 题。