AT_aalc001_k 多重集合

有一个整数多重集 $S$。最初，$S$ 包含 $N$ 个元素 $A_1, A_2, \ldots, A_N$。 现在要处理 $Q$ 个查询。每个查询有以下三种类型之一： - `1 x`：向 $S$ 中添加 $1$ 个 $x$。 - `2 x`：从 $S$ 中删除 $1$ 个 $x$。保证在处理此查询之前，$S$ 中至少有 $1$ 个 $x$。 - `3`：设 $x_1, x_2, \ldots, x_k$ 为升序排列后（含重复）的 $S$ 中所有元素序列。输出 $ \displaystyle \sum_{i=1}^{k} i x_i $，并对 $998244353$ 取模。 当 $S$ 为空时，$k=0$，此时上述和定义为 $0$。

输入从标准输入读入，格式如下： > $N \ Q \ A_1 \ A_2 \ \ldots \ A_N \ \mathrm{query}_1 \ \mathrm{query}_2 \ \vdots \ \mathrm{query}_Q$ 每个查询的格式如下： > $1 \ x$ > $2 \ x$ > $3$

设类型为 $3$ 的查询有 $q$ 次。输出 $q$ 行，第 $j$ 行输出第 $j$ 次类型为 $3$ 查询的答案。

### 样例解释 1 将初始 $S$ 升序排列得到 $(1,2,3,3)$，所以第一个查询输出 $1 \times 1 + 2 \times 2 + 3 \times 3 + 4 \times 3 = 26$。 ### 样例解释 2 对于类型为 $3$ 的查询，此时 $S$ 为空，因此输出 $0$。 ### 数据范围 - $1 \leq N \leq 2 \times 10^5$ - $1 \leq Q \leq 2 \times 10^5$ - $0 \leq A_i \leq 10^9$ - 对于类型 $1$ 和 $2$ 的查询，$0 \leq x \leq 10^9$ - 对于每个类型 $2$ 查询，在处理之前，$S$ 中至少有 $1$ 个 $x$ - 所有输入值均为整数。 由 ChatGPT 5 翻译