Yujin 正在和荷官玩一个纸牌游戏。

荷官有一副包含 $n$ 张牌的牌堆，每张牌的正面要么是黑桃（$\spadesuit$），要么是红桃（$\heartsuit$）。牌堆最初以随机顺序叠放，背面朝上。荷官知道所有牌的正面，但 Yujin 不知道。

在游戏开始前，荷官会喊出一个 $1$ 到 $n$ 之间的整数 $k$。Yujin 的目标是找到从上往下数的第 $k$ 张黑桃牌。游戏过程如下：

• 荷官按顺序将牌一张一张地放在桌子上，背面朝上。
• 在任何时候，Yujin 都可以支付给荷官一枚硬币并大喊“停！”（在荷官放下最后一张牌后也可以立即这样做）。
• 当 Yujin 大喊“停！”时，荷官会统计目前已放下的黑桃和红桃牌的数量，并在继续放牌之前将这两个数字告诉 Yujin。

当荷官放完所有牌后，牌会被重新排列回原来的顺序。此时 Yujin 有一次机会猜测答案。Yujin 可以做出以下两种声明之一：

• 声明牌堆中黑桃牌的总数少于 $k$ 张。
• 指出某一张特定的牌，并声明它是从上往下数的第 $k$ 张黑桃牌。

如果 Yujin 的声明正确，她就赢了；否则，荷官获胜。

Yujin 不喜欢输，所以她想使用一种能保证她在任何情况下都能获胜的策略。例如，Yujin 在荷官每放下一张牌时都喊“停！”的策略，可以确保她总是能找到第 $k$ 张黑桃牌，因此这是一个获胜策略。

Yujin 决定使用需要支付最少硬币的获胜策略。她支付的硬币数量必须小于或等于任何其他获胜策略，并且可以证明这样的策略是存在的。

给定牌的初始排列。对于 $1$ 到 $n$ 的每一个 $k$ 值，确定 Yujin 使用她的获胜策略需要支付给荷官多少枚硬币。

输入格式

第一行包含牌的数量 $n$ ($1 \le n \le 10^6$)。

第二行包含一个长度为 $n$ 的字符串，表示牌堆。第 $i$ 个字符表示从上往下数第 $i$ 张牌的花色，其中 S 代表黑桃，H 代表红桃。

输出格式

输出一行，包含 $n$ 个由空格分隔的整数。第 $i$ 个整数表示当 $k = i$ 时 Yujin 需要支付给荷官的硬币数量。

样例

样例输入 1

10
HSHHHHHHSH

样例输出 1

2 8 5 3 2 1 1 1 1 1

样例输入 2

10
SSHHSSHHHS

样例输出 2

1 1 3 2 5 3 2 1 1 1

样例输入 3

10
SSSSSSSSSS

样例输出 3

1 1 1 1 1 1 1 1 1 1

说明

在第一个样例中，考虑荷官喊出 $k = 2$ 的情况：

• Yujin 在荷官放下第 $2$ 张牌后喊“停！”。荷官告知 Yujin 到目前为止他放下了 $1$ 张红桃和 $1$ 张黑桃。
• 此后，Yujin 在荷官放下第 $3$ 张、第 $4$ 张、……、第 $9$ 张牌时都喊“停！”。荷官同样告知她已放下的红桃和黑桃数量。
• 一旦荷官放完了所有的牌，Yujin 就可以猜出从上往下数的第 $9$ 张牌是黑桃。

通过上述过程，Yujin 将支付 $8$ 枚硬币来找到第 $k$ 张黑桃牌。