Byteman 决定开车去山上兜风。他带了一张地图，但他无法在地图上定位自己。

地图上的道路由 $n$ 个转弯组成，每个转弯都是向左或向右的 90° 转弯。为简单起见，我们可以用一个由 L 和/或 P 组成的 $n$ 个字符的字符串来表示地图。

假设 Byteman 正处于第 $i$ 个转弯前（但他可能不知道这是第 $i$ 个转弯），我们用 $a_i$ 表示 Byteman 为了确定自己在地图上的位置所必须经过的转弯数量。

我们通过一个例子来解释 $a_i$ 的含义。假设地图上的道路由字符串 LLPPLPL 表示（L 代表左转，P 代表右转，因为在波兰语中 "prawo" 意为右）。如果 Byteman 正处于第二个转弯前，在通过该转弯之前，他知道自己可能处于第 1、2、5 或 7 个转弯前（因为他看到前方是一个左转）。通过该转弯后，Byteman 看到一个右转 P，这意味着他最初不可能处于第一个转弯前（因为随后的转弯是左转），也不可能处于最后一个转弯前（因为后面是道路终点）。因此，他知道自己处于地图上第三个或第六个转弯前。通过该转弯后，Byteman 看到一个右转 P，这意味着他最初不可能处于第五个转弯前。这得出一个观察结果：在通过两个转弯后，Byteman 处于第四个转弯前，因此 $a_2 = 2$。

编写一个程序：

• 从标准输入读取地图描述，
• 确定 $1 \le i \le n$ 的 $a_i$ 值，
• 将结果写入标准输出。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 500\,000$)。第二行包含道路的描述——$n$ 个字母 L 和/或 P，中间没有空格。

输出格式

你的程序应向输出写入恰好 $n$ 行。第 $i$ 行应包含一个整数：$a_i$。

样例

输入 1

7
LLPPLPL

输出 1

1
2
1
2
2
2
1