子集和为 K 的个数

题目描述

我们有一个盒子，初始为空。

按照输入中给出的顺序，总共执行 $Q$ 次以下两种类型的操作。

类型 1：+ x —— 向盒子中放入一个写有整数 $x$ 的球。

类型 2：- x —— 从盒子中取走一个写有整数 $x$ 的球。保证在执行该操作之前，盒子中确实存在一个写有整数 $x$ 的球。

对于每次操作后的盒子，解决以下问题：

从盒子中取出若干个球，求使球上写有的整数之和恰好为 $K$ 的取法数，对 $998244353$ 取模。

盒子中的所有球都是可区分的（互不相同）。

输入格式

输入按以下格式从标准输入给出，其中 $\rm{Query}_i$ 表示第 $i$ 次操作：

$Q$ $K$
$\rm{Query}_1$
$\rm{Query}_2$
$\vdots$
$\rm{Query}_Q$

输出格式

输出 $Q$ 行。

第 $i$ 行应包含前 $i$ 次操作完成后的答案。

样例

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

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

这个输入包含 $15$ 次操作。

最后一次操作后，盒子中装有 $(5,10,1,3,1,7,4)$ 这些球。

使和为 $10$ 的取球方式共有五种：

$5+1+3+1$（第 1、3、4、5 个球）

$5+1+4$（第 1、3、7 个球）

$5+1+4$（第 1、5、7 个球）

$10$（第 2 个球）

$3+7$（第 4、6 个球）

数据范围

• 输入中的所有值均为整数。
• $1 \le Q \le 5000$
• $1 \le K \le 5000$
• 对于每个类型 1 操作，$1 \le x \le 5000$。
• 所有操作均满足题目描述中的条件。