AT_past202309_n ソートと関数

对于一个由正整数组成的多重集 $S$，定义函数 $f(S)$ 如下： - 首先，令 $A=(A_0,A_1,\ldots,A_{|S|-1})$ 为 $S$ 的元素按升序排序后的列表。 - 然后，$f(S)=\displaystyle \sum_{i=0}^{|S|-1} K^i A_i$。常数 $K$ 将由输入给出。 - 如果 $S$ 为空集，则 $f(S)=0$。 现有一个初始为空的多重集 $T$。将对这个集合总共进行 $Q$ 次如下操作： > + $x$ 向 $T$ 中加入一个 $x$。 > - $x$ 从 $T$ 中移除一个 $x$。保证此时 $T$ 中至少有一个 $x$。 每次操作后，输出此时 $f(T)$ 对 $998244353$ 取模后的值。

从标准输入读取数据，格式如下： > $Q$ $K$ > $ope_1$ > $ope_2$ > $\vdots$ > $ope_Q$ 其中 $ope_i$ 表示第 $i$ 次操作。

共输出 $Q$ 行。 第 $i$ 行输出第 $i$ 次操作后 $f(T)$ 对 $998244353$ 取模的结果。

### 样例解释 1 - 第一次操作向 $T$ 加入 $7$。 - 此时 $T=\{7\}$，$f(T)=7$。 - 第二次操作移除 $7$。 - 此时 $T=\{\}$，$f(T)=0$。 - 第三次操作加入 $2$。 - 此时 $T=\{2\}$，$f(T)=2$。 - 第四次操作加入 $3$。 - 此时 $T=\{2,3\}$，$f(T)=8$。 - 第五次操作移除 $2$。 - 此时 $T=\{3\}$，$f(T)=3$。 - 第六次操作加入 $3$。 - 此时 $T=\{3,3\}$，$f(T)=9$。 - 第七次操作加入 $5$。 - 此时 $T=\{3,3,5\}$，$f(T)=29$。 - 第八次操作移除 $3$。 - 此时 $T=\{3,5\}$，$f(T)=13$。 - 第九次操作加入 $998244352$。 - 此时 $T=\{3,5,998244352\}$，$f(T)=3992977421$，对 $998244353$ 取模输出 $9$。 - 第十次操作加入 $5$。 - 此时 $T=\{3,5,5,998244352\}$，$f(T)=7985954849$，对 $998244353$ 取模输出 $25$。 ### 数据范围 - $Q$ 和 $K$ 为整数。 - $1 \le Q \le 3 \times 10^5$ - $1 \le K < 998244353$ - 每次操作中的 $x$ 为整数。 - 对于每次 `+` 操作，$1 \le x < 998244353$。 - 对于每次 `-` 操作，保证 $T$ 中有一个及以上 $x$。 由 ChatGPT 5 翻译