你有一排排列好的卡片。每张卡片都有一个数值，且属于以下两种类型之一：加法卡或乘法卡。

计算一排卡片的得分方式如下：初始分数为零。然后，从左到右处理这些卡片。

如果是加法卡，将分数加上卡片的数值。如果是乘法卡，将分数乘以卡片的数值。

最终得分即为处理完所有卡片后得到的分数。

对于所有可能的子序列长度，你想要知道：对于该长度（如果由于乘法卡数量限制导致无法达到该长度，则为更小的长度），在保持原始顺序的前提下，你能获得的最高得分是多少？注意，选择卡片后不能重新排列它们。此外，子序列不必是连续的。

输入格式

输入的第一行包含两个整数 $n$ ($2 \le n \le 2 \cdot 10^5$) 和 $k$ ($0 \le k \le n$)，其中 $n$ 是卡片的数量，$k$ 是你可以使用的乘法卡的最大数量。

接下来的 $n$ 行，每行包含一个字符 $s$（$s$ 为 'a' 或 'm'，均为小写）和一个整数 $v$ ($2 \le v \le 1,000$)，其中 $s$ 表示该卡片是加法卡（'a'）还是乘法卡（'m'），$v$ 是卡片的数值。

保证所有乘法卡数值的乘积不超过 $10^9$。

输出格式

输出 $n$ 行。在每一行中，输出长度分别为 1, 2, 3, 直到 $n$ 的子序列所能达到的最高得分。

样例

样例输入 1

4 3
a 3
m 2
a 8
m 3

样例输出 1

8
24
33
42

样例输入 2

6 1
a 2
m 5
a 2
a 2
m 3
a 3

样例输出 2

3
10
13
18
21
21