AT_past202309_n ソートと関数

正整数の多重集合(同一の要素を複数個含むことが許された集合) $ S $ に対して、関数 $ f(S) $ を以下のように定義します。 - まず、 $ S $ の要素を昇順に並べた数列を $ A=(A_0,A_1,...,A_{|S|-1}) $ とします。 - そして、 $ f(S)=\displaystyle \sum_{i=0}^{|S|-1} K^i A_i $ と定めます。この定数 $ K $ は入力で与えられます。 - ただし、 $ S $ が空の場合、 $ f(S)=0 $ とします。 最初空の多重集合 $ T $ があります。この集合に対して以下の操作を合わせて $ Q $ 回行います。 > + $ x $ $ T $ に $ x $ を $ 1 $ つ追加する。 > - $ x $ $ T $ から $ x $ を $ 1 $ つ削除する。但し、このとき $ T $ に $ x $ が $ 1 $ つ以上存在することが保証される。 各操作を行った後、その時点での $ f(T) $ の値を $ 998244353 $ で割った余りを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ Q $ $ K $ $ ope_1 $ $ ope_2 $ $ \vdots $ $ ope_Q $ 但し、 $ ope_i $ は $ i $ 回目に行う操作を表す。

全体で $ Q $ 行出力せよ。 そのうち $ i $ 行目には、 $ i $ 回目の操作を終えた時点での $ f(T) $ の値を $ 998244353 $ で割った余りを出力せよ。

### Sample Explanation 1 - $ 1 $ 個目の操作では、 $ T $ に $ 7 $ を $ 1 $ つ追加します。 - このとき、 $ T=\{7\} $ であり、 $ f(T)=7 $ です。 - $ 2 $ 個目の操作では、 $ T $ から $ 7 $ を $ 1 $ つ削除します。 - このとき、 $ T=\{\} $ であり、 $ f(T)=0 $ です。 - $ 3 $ 個目の操作では、 $ T $ に $ 2 $ を $ 1 $ つ追加します。 - このとき、 $ T=\{2\} $ であり、 $ f(T)=2 $ です。 - $ 4 $ 個目の操作では、 $ T $ に $ 3 $ を $ 1 $ つ追加します。 - このとき、 $ T=\{2,3\} $ であり、 $ f(T)=8 $ です。 - $ 5 $ 個目の操作では、 $ T $ から $ 2 $ を $ 1 $ つ削除します。 - このとき、 $ T=\{3\} $ であり、 $ f(T)=3 $ です。 - $ 6 $ 個目の操作では、 $ T $ に $ 3 $ を $ 1 $ つ追加します。 - このとき、 $ T=\{3,3\} $ であり、 $ f(T)=9 $ です。 - $ 7 $ 個目の操作では、 $ T $ に $ 5 $ を $ 1 $ つ追加します。 - このとき、 $ T=\{3,3,5\} $ であり、 $ f(T)=29 $ です。 - $ 8 $ 個目の操作では、 $ T $ から $ 3 $ を $ 1 $ つ削除します。 - このとき、 $ T=\{3,5\} $ であり、 $ f(T)=13 $ です。 - $ 9 $ 個目の操作では、 $ T $ に $ 998244352 $ を $ 1 $ つ追加します。 - このとき、 $ T=\{3,5,998244352\} $ であり、 $ f(T)=3992977421 $ なので、これを $ 998244353 $ で割った余りである $ 9 $ を出力してください。 - $ 10 $ 個目の操作では、 $ T $ に $ 5 $ を $ 1 $ つ追加します。 - このとき、 $ T=\{3,5,5,998244352\} $ であり、 $ f(T)=7985954849 $ なので、これを $ 998244353 $ で割った余りである $ 25 $ を出力してください。 ### Constraints - $ Q,K $ は整数 - $ 1 \le Q \le 3 \times 10^5 $ - $ 1 \le K < 998244353 $ - 全ての操作について、 $ x $ は整数 - 操作 `+` について、 $ 1 \le x < 998244353 $ - 操作 `-` について、その時点で $ T $ に $ x $ が $ 1 $ つ以上存在する。