Compute the score for a row of cards as follows: Initially, the score is zero. Then, process the cards from left to right.
If it is an add card, increase the score by the card’s value. If it is a multiply card, multiply the score by the card’s value.
The final score is what you get after processing all the cards.
For all possible subsequence sizes, you’d like to know: what is the maximum possible score you can attain for a subsequence of that size (or fewer, if that size isn’t possible due to the limit on the number of multiply cards), maintaining their original order? Note, you can’t rearrange the cards after choosing them. Also, a subsequence doesn’t have to be contiguous.
The first line of input contains two integers $n$ ($2 \le n \le 2\cdot 10^5$) and $k$ ($0 \le k \le n$), where $n$ is the number of cards, and $k$ is the maximum number of multiply cards you can use.
Each of the next $n$ lines contains a letter $s$ ($s$ is either ‘a’ or ‘m’, always lower case) and an integer $v$ ($2 \le v \le 1\, 000$), where $s$ indicates whether the card is an add card (‘a’) or a multiply card (‘m’), and $v$ is the value of the card.
It is guaranteed that the product of all multiply cards is at most $10^9$.
Output $n$ lines. On each line, output the maximum score you can achieve for a subsequence of length at most $1$, $2$, $3$, and so on, up to $n$.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 3 a 3 m 2 a 8 m 3 |
8 24 33 42 |
| Sample Input 2 | Sample Output 2 |
|---|---|
6 1 a 2 m 5 a 2 a 2 m 3 a 3 |
3 10 13 18 21 21 |