题目内容

在量子能量实验中，系统使用一个初始为 0 的非负整数 $E$ 表示能量储备。你将依次执行一串由四种指令组成的操作序列，每个指令用单个字符表示，含义如下：

• '+'：将 $E$ 增加 1；
• '-'：将 $E$ 减少 1，但能量不能低于 0（若 $E$ 为 0 则该指令不产生效果）；
• '*'：将 $E$ 乘以 2；
• '/'：将 $E$ 除以 2 并向下取整。

定义 $E$ 的「核心电荷数」为 $E$ 在二进制表示中数字 1 的个数（即 popcount）。初始时 $E=0$，核心电荷数为 0。

对于操作序列中的每一个指令，模拟其作用并实时输出当前 $E$ 对应的核心电荷数。

约束条件：指令数量 $n$ 满足 $1 \le n \le 10^6$，字符串 $s$ 仅由 '+', '-', '*', '/' 四种字符组成，长度恰为 $n$。整个过程中 $E$ 始终保持非负整数。

输入描述

第一行包含一个整数 $n$（$1 \le n \le 10^6$），表示指令的数量。 第二行包含一个长度为 $n$ 的字符串 $s$，由字符 '+', '-', '*', '/' 组成（不含空格），表示指令序列。

输出描述

输出 $n$ 行，每行一个整数，依次对应每个指令执行完毕后当前 $E$ 的核心电荷数。

样例1

输入

6
++*+-/

输出

1
1
1
2
1
1

说明

初始 $E=0$，核心电荷数为 0。

1. 执行 '+'：$E=1$，二进制为 $1$，核心电荷数变为 1。
2. 执行 '+'：$E=2$，二进制为 $10$，核心电荷数仍为 1。
3. 执行 '*'：$E=4$，二进制为 $100$，核心电荷数仍为 1。
4. 执行 '+'：$E=5$，二进制为 $101$，核心电荷数变为 2。
5. 执行 '-'：$E=4$，二进制为 $100$，核心电荷数回到 1。
6. 执行 '/'：$E=2$，二进制为 $10$，核心电荷数保持 1。

样例2

输入

9
+++++-*-/

输出

1
1
2
1
2
1
1
3
2

说明

初始 $E=0$。

• '+'：$E=1$ ($1$)，电荷数 1。
• '+'：$E=2$ ($10$)，电荷数 1。
• '+'：$E=3$ ($11$)，电荷数 2。
• '+'：$E=4$ ($100$)，电荷数 1。
• '+'：$E=5$ ($101$)，电荷数 2。
• '-'：$E=4$ ($100$)，电荷数 1。
• '*'：$E=8$ ($1000$)，电荷数 1。
• '-'：$E=7$ ($111$)，电荷数 3。
• '/'：$E=3$ ($11$)，电荷数 2。

该序列包含了连续进位、借位以及乘除等多种情况。

样例3

输入

5
-/*+-

输出

0
0
0
1
0

说明

测试边界情况：初始 $E=0$。

• '-'：$E=0$ 不能减少，仍为 0，电荷数 0。
• '/'：$0/2$ 仍为 0，电荷数 0。
• '*'：$0 \times 2 = 0$，电荷数 0。
• '+'：$E=1$，电荷数 1。
• '-'：$E=0$，电荷数 0。