问题描述

在一个宁静的小镇上，居民们依赖路灯来照亮夜晚的街道，确保安全和温暖。小镇上的路灯数量为 $n$（都在一条直线上），每个路灯的朝向决定了它能照亮的范围：有的朝向东边，有的朝向西边。每个路灯的照亮值取决于它照亮的范围内有多少其他路灯。整个小镇的 “总照亮值” 是所有路灯照亮值的总和。

例如，路灯的初始朝向为 EWWEE，其中 E 代表向东，W 代表向西，那么每个路灯的照亮值为 $[4,1,2,1,0]$，整条街道的总照亮值为 $4+1+2+1+0=8$ 。

为了让小镇的夜晚更加明亮，你发现自己拥有一种能力，可以在每次观察的过程中，最多改变 $k$ 个路灯的朝向（从东转为西，或从西转为东）。你的任务是利用这一能力，找出在每种情况下（$k$ 从 $1$ 到 $n$）所能达到的最大 “总照亮值”。

向西即向左，向东即向右，左西右东。

输入格式

• 第一行输入一个整数 $n$，表示路灯的数量 $(1 ≤ n ≤ 10^5)$。
• 第二行输入一个字符串 $s$，长度为 $n$，仅包含字符 E 和 W，表示每个路灯的初始朝向。

输出格式

• 对于每个 $k$ 从 $1$ 到 $n$，输出一个整数，表示最多可以改变 $k$ 个路灯的方向时，小镇的最大总照亮值。
• 对于每个 $k$，你的选择都是独立的。

样例输入

3
WWE

样例输出

3 5 5

样例输入

5
EWWEE

样例输出

12 14 16 16 16

说明

在第一个测试用例中：

• $k=1$ ：更改第 $1$ 个路灯的方向变成 EWE 。总值为 $2+1+0=3$ 。
• $k=2$ ：更改第 $1$ 个和第 $3$ 个路灯的方向变成 EWW。总值为 $2+1+2=5$ 。
• $k=3$ ：更改第 $1$ 个和第 $3$ 个路灯的方向变成 EWW。总值为 $2+1+2=5$ 。
• 请注意，您是最多改变 $k$ 个路灯的方向，不是必须改变 $k$ 个。

在第二个测试用例中：

• 先后更改第 $5$ 个、第 $2$ 个和第 $4$ 个路灯即可。