这是问题的简单版本。版本之间的唯一区别是 $$$n$$$ 和 $$$m$$$ 的上限。在此版本中,$$$n \le 500$$$ 和 $$$m \le 500$$$。
你有一群 $$$n$$$ 圣诞驯鹿。第 $$$i$$$ 驯鹿的力量为 $$$2^{c_i}$$$。
一组 $$$k$$$ 圣诞驯鹿的承载能力计算如下:
- 驯鹿的强项按非升序排列。我们将排序后的优势列表表示为 $$$c'_1, c'_2, \dots, c'_k$$$,其中 $$$c'_i \ge c'_{i+1}$$$;
- 那么这群驯鹿的承载能力就等于$$$c'_1 + \lfloor\frac{c'_2}{2}\rfloor + \lfloor\frac{c'_3}{4}\rfloor + \dots + \lfloor\frac{c'_k}{2^{k - 1}}\rfloor$$$。
请注意,某些驯鹿对群体的承载能力的贡献可能为零。
您必须处理三种类型的查询:
- 向鹿群中添加一头强度为 $$$2^x$$$ 的驯鹿;
- 从驯鹿群中移除一头强度为$$$2^x$$$的驯鹿;
- 计算从鹿群中选择部分驯鹿(可能是全部)的方法数,使得所选群体的承载能力为 至少 $$$x$$$.
如果鹿群中有多只强度相同的驯鹿,则认为它们是不同的。例如,如果你有两只驯鹿,每只力量为 $$$1$$$,你需要计算选择一组承载能力至少为 $$$1$$$ 的方法,则有 $$$3$$$ 的选择方法:选择第一只驯鹿、第二只驯鹿或两者都选择。
输入
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 500$$$) – 分别是鹿群中驯鹿的初始数量和查询数量。
第二行包含 $$$n$$$ 整数 $$$c_1, c_2, \dots, c_n$$$ ($$$0 \le c_i \le 60$$$) 表示驯鹿群中驯鹿的强度:第 $$$i$$$ 驯鹿的强度为 $$$2^{c_i}$$$。
接下来的 $$$m$$$ 行采用以下格式之一描述查询:
- $$$1$$$ $$$x$$$ ($$$0 \le x \le 60$$$) — 将一头强度等于 $$$2^x$$$ 的驯鹿添加到鹿群中;
- $$$2$$$ $$$x$$$ ($$$0 \le x \le 60$$$) — 从鹿群中移除一头强度等于 $$$2^x$$$ 的驯鹿;
- $$$3$$$ $$$x$$$ ($$$1 \le x \le 10^{18}$$$) — 计算从鹿群中选择一组驯鹿的方法数,使得所选组的承载能力至少为 $$$x$$$。
对输入的附加约束:每当给出 $$$2$$$ 类型的查询时,鹿群当前至少包含一头强度等于 $$$2^x$$$ 的驯鹿。
输出
对于第三种类型的每个查询,打印一个整数 - 从鹿群(可能是整个鹿群)中选择一组驯鹿的方法数量,使得所选组的承载能力至少为 $$$x$$$。因为它可能很大,所以打印它对 $$$998244353$$$ 取模。
示例
输入复制
3 72 1 13 53 61 23 63 52 13 5
输出复制
3 0 4 10 4
输入复制
5 56 9 2 3 53 5181 42 91 103 1016
输出复制
12 32
输入复制
5 2056 58 31 56 573 5841336999156136981 263 7189345176981336441 433 8537955255658039343 3711289078856020071 541 253 122834517782167712 253 2698374054237693401 03 813328844310754681 233 42569849624440223 6684080039827661023 9234102226533745503 3403137432353114153 5501662824407757693 445344499963496530
输出复制
0 0 0 24 496 128 416 992 0 0 320 0 0
注意
让我们考虑第一个例子。最初,有三只驯鹿,其力量分别为 $$$4$$$、$$$2$$$ 和 $$$2$$$。
- 在第一次查询时,你必须计算有多少种方法来选择一个承载能力至少为$$$5$$$的组。共有三个可能的组:$$$\{1, 2\}$$$(包含 $$$1$$$-st 和 $$$2$$$-nd 驯鹿的组)、$$$\{1, 2, 3\}$$$ 和 $$$\{1, 3\}$$$;
- 在第二次查询时,你必须计算有多少种方法来选择一个承载能力至少为$$$6$$$的组。即使整个牛群的承载能力等于 $$$4 + \lfloor\frac{2}{2}\rfloor + \lfloor\frac{2}{4}\rfloor = 5$$$,因此没有合适的方法来选择群体;
- 在第三次查询期间,添加了一头力量为$$$4$$$的驯鹿。我们将其表示为第 $$$4$$$ 驯鹿;
- 在第四次查询期间,可能的组为 $$$\{1, 4\}$$$、$$$\{1, 2, 4\}$$$、$$$\{1, 3, 4\}$$$ 和 $$$\{1, 2, 3, 4\}$$$;
- 在第五次查询期间,有$$$10$$$可能的组;
- 在第六次查询期间,一头强度为$$$2$$$的驯鹿被移除。假设这是第 $$$2$$$-nd 驯鹿,那么只剩下 $$$1, 3, 4$$$ 驯鹿;
- 在第七次查询时,你必须计算选择承载能力至少为$$$5$$$的组的方法数。有四个可能的组:$$$\{1, 3\}$$$、$$$\{1, 4\}$$$、$$$\{1, 3, 4\}$$$、$$$\{3, 4\}$$$。