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 翻译