AT_aalc001_k 多重集合

There is a multiset $ S $ of integers. Initially, $ S $ has $ N $ elements $ A_1,A_2,\ldots,A_N $ . Process $ Q $ queries. Each query is of one of the following $ 3 $ types: - `1 x`: Add $ 1 $ occurrence of $ x $ to $ S $ . - `2 x`: Remove $ 1 $ occurrence of $ x $ from $ S $ . It is guaranteed that immediately before this query is processed, $ S $ contains at least $ 1 $ occurrence of $ x $ . - `3`: Let $ x_1,x_2,\ldots,x_k $ be the sequence obtained by sorting all elements of $ S $ in ascending order, including duplicates. Print $ \displaystyle \sum_{i=1}^{k} i x_i $ modulo $ 998244353 $ . When $ S $ is empty, $ k=0 $ , and the sum above is defined to be $ 0 $ .

The input is given from Standard Input in the following format: > $ N $ $ Q $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $ $ \mathrm{query}_1 $ $ \mathrm{query}_2 $ $ \vdots $ $ \mathrm{query}_Q $ Each query is given in one of the following formats: > $ 1 $ $ x $ > $ 2 $ $ x $ > $ 3 $

Let $ q $ be the number of type $ 3 $ queries. Print $ q $ lines. The $ j $ -th line should contain the answer to the $ j $ -th type $ 3 $ query.

### Sample Explanation 1 Sorting the initial elements of $ S $ in ascending order gives $ (1,2,3,3) $ , so for the first query, print $ 1 \times 1+2 \times 2+3 \times 3+4 \times 3=26 $ . ### Sample Explanation 2 For query $ 3 $ , $ S $ is empty at that time, so print $ 0 $ . ### Constraints - $ 1 \leq N \leq 2 \times 10^5 $ - $ 1 \leq Q \leq 2 \times 10^5 $ - $ 0 \leq A_i \leq 10^9 $ - For queries of types $ 1 $ and $ 2 $ , $ 0 \leq x \leq 10^9 $ - Immediately before each type $ 2 $ query, $ S $ contains at least $ 1 $ occurrence of $ x $ . - All numerical values in the input are integers.