/ 
実行時間制限: 4 sec / メモリ制限: 1024 MiB
問題文
正整数の多重集合(同一の要素を複数個含むことが許された集合) 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 は整数
- 1 \le Q \le 3 \times 10^5
- 1 \le K < 998244353
- 全ての操作について、 x は整数
- 操作
+について、 1 \le x < 998244353 - 操作
-について、その時点で T に x が 1 つ以上存在する。
入力
入力は以下の形式で標準入力から与えられる。
Q K ope_1 ope_2 \vdots ope_Q
但し、 ope_i は i 回目に行う操作を表す。
出力
全体で Q 行出力せよ。
そのうち i 行目には、 i 回目の操作を終えた時点での f(T) の値を 998244353 で割った余りを出力せよ。
入力例 1
10 2 + 7 - 7 + 2 + 3 - 2 + 3 + 5 - 3 + 998244352 + 5
出力例 1
7 0 2 8 3 9 29 13 9 25
- 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 を出力してください。
Problem Statement
For a multiset (set with duplicate elements allowed) S of positive integers, let us define the function f(S) as follows.
- First, let A=(A_0,A_1,...,A_{|S|-1}) be the sorted list of the elements of S in ascending order.
- Then, let f(S)=\displaystyle \sum_{i=0}^{|S|-1} K^i A_i. This constant K is given from the input.
- Here, let f(S)=0 if S is empty.
There is an initially empty multiset T. Let us perform the following operations on this set Q times in total.
+ X
Add one instance of x to T.
- x
Remove one instance of x from T. It is guaranteed that at least one instance of x exists in T at this time.
After each operation, find the value of f(T) modulo 998244353 at that time.
Constraints
- Q and K are integers.
- 1 \le Q \le 3 \times 10^5
- 1 \le K < 998244353
- For every operation, x is an integer.
- For each operation
+, 1 \le x < 998244353. - For each operation
-, there is one or more instances of x in T at that time.
Input
The input is given from Standard Input in the following format:
Q K ope_1 ope_2 \vdots ope_Q
Here, ope_i represents the i-th operation to be performed.
Output
Print Q lines in total.
The i-th line should contain the value of f(T) modulo 998244353 at the end of the i-th operation.
Sample Input 1
10 2 + 7 - 7 + 2 + 3 - 2 + 3 + 5 - 3 + 998244352 + 5
Sample Output 1
7 0 2 8 3 9 29 13 9 25
- The first operation adds one instance of 7 to T.
- Now, T=\{7\} and f(T)=7.
- The second operation removes one instance of 7 from T.
- Now, T=\{\} and f(T)=0.
- The third operation adds one instance of 2 to T.
- Now, T=\{2\} and f(T)=2.
- The fourth operation adds one instance of 3 to T.
- Now, T=\{2,3\} and f(T)=8.
- The fifth operation removes one instance of 2 from T.
- Now, T=\{3\} and f(T)=3.
- The sixth operation adds one instance of 3 to T.
- Now, T=\{3,3\} and f(T)=9.
- The seventh operation adds one instance of 5 to T.
- Now, T=\{3,3,5\} and f(T)=29.
- The eighth operation removes one instance of 3 from T.
- Now, T=\{3,5\} and f(T)=13.
- The ninth operation adds one instance of 998244352 to T.
- Now, T=\{3,5,998244352\} and f(T)=3992977421, so print this modulo 998244353, that is, 9.
- The tenth operation adds one instance of 5 to T.
- Now, T=\{3,5,5,998244352\} and f(T)=7985954849, so print this modulo 998244353, that is, 25.