AT_past202309_n ソートと関数

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.

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.

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 Explanation 1 - 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 $ . ### 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.