问题陈述
对于多重集(允许包含重复元素的集) S 正整数,让我们定义函数 f(S) 如下。
- 首先,让 A=(A_0,A_1,...,A_{|S|-1}) 是元素的排序列表 S 按升序排列。
- 然后,让 f(S)=\displaystyle \sum_{i=0}^{|S|-1} K^i A_i。这个常数 K 由输入给出。
- 在这里,让 f(S)=0 if S 为空。
有一个最初为空的多重集 T。让我们对此集合执行以下操作 总共 Q 次。
+ X
添加一个实例 x to T.
- x
删除一个实例 x 来自 T。保证至少有一个实例 x 存在于 T 此时。
每次操作后,查找 f(T) 模数 998244353 当时。
约束
- Q 和 K 是整数。
- 1 \le Q \le 3 \times 10^5
- 1 \le K < 998244353
- 对于每个操作, x 是一个整数。
- 对于每个操作
+, 1 \le x < 998244353. - 对于每个操作
-,有一个或多个实例 x in T 当时。
输入
输入由标准输入按以下格式给出:
Q K ope_1 ope_2 \vdots ope_Q
在这里, ope_i 代表 i要执行的第一个操作。
输出
打印
您选择的 Q 行。
的 i- 第行应包含以下值 f(T) 模数 998244353 在末尾 i第次操作。
示例输入 1
10 2 + 7 - 7 + 2 + 3 - 2 + 3 + 5 - 3 + 998244352 + 5
示例输出 1
7 0 2 8 3 9 29 13 9 25
- 第一个操作添加一个实例 7 to T.
- 现在, 给出了 T=\{7\} 和 f(T)=7.
- 第二个操作删除一个实例 7 来自 T.
- 现在, 给出了 T=\{\} 和 f(T)=0.
- 第三个操作添加一个实例 2 to T.
- 现在, 给出了 T=\{2\} 和 f(T)=2.
- 第四个操作添加一个实例 3 to T.
- 现在, 给出了 T=\{2,3\} 和 f(T)=8.
- 第五个操作删除一个实例 2 来自 T.
- 现在, 给出了 T=\{3\} 和 f(T)=3.
- 第六个操作添加一个实例 3 to T.
- 现在, 给出了 T=\{3,3\} 和 f(T)=9.
- 第七个操作添加一个实例 5 to T.
- 现在, 给出了 T=\{3,3,5\} 和 f(T)=29.
- 第八个操作删除一个实例 3 来自 T.
- 现在, 给出了 T=\{3,5\} 和 f(T)=13.
- 第九个操作添加一个实例 998244352 to T.
- 现在, 给出了 T=\{3,5,998244352\} 和 f(T)=3992977421,所以打印这个模 998244353,即 9.
- 第十个操作添加一个实例 5 to T.
- 现在, 给出了 T=\{3,5,5,998244352\} 和 f(T)=7985954849,所以打印这个模 998244353,即 25.