2482 - 玩个球
Description

维护一个箱子,有 Q 个操作,分为如下类型:

-   `+ x`,表示向箱子中扔一个写有数字 x 的球。

-   `- x`,表示从箱子中拿出一个写有数字 x 的球(保证存在这样的球)。

每一次操作后,计算:有多少种从箱子里拿球的方法,使得拿的球上写有的数字的总和为 K(并不需要真正拿出球)?答案对 998244353 取余。


Input

第一行两个数字Q,K分别表示操作的次数和数字的总和

接下来Q行,表示操作

Output

针对每次操作,输出总和为K的方案数

Examples

Input

15 10
+ 5
+ 2
+ 3
- 2
+ 5
+ 10
- 3
+ 1
+ 3
+ 3
- 5
+ 1
+ 7
+ 4
- 3

Output

0
0
1
0
1
2
2
2
2
2
1
3
5
8
5
Hint

- 1\ \le\ Q\ \le\ 5000

- 1\ \le\ K\ \le\ 5000

- 1\ \le\ x\ \le\ 5000


题目参数
Time Limit 1 second
Memory Limit 128 MB
提交次数 95
通过次数 15