CF2182F2 Christmas Reindeer (hard version)

This is the hard version of the problem. The only difference between the versions is the upper bound on $ n $ and $ m $ . In this version, $ n \le 3 \cdot 10^5 $ and $ m \le 3 \cdot 10^5 $ . You have a herd of $ n $ Christmas reindeer. The strength of the $ i $ -th reindeer is $ 2^{c_i} $ . The carrying capacity of a group of $ k $ Christmas reindeer is calculated as follows: - the strengths of the reindeer are sorted in non-increasing order. Let's denote the sorted list of strengths as $ c'_1, c'_2, \dots, c'_k $ , where $ c'_i \ge c'_{i+1} $ ; - then, the carrying capacity of this group of reindeer is equal to $ c'_1 + \lfloor\frac{c'_2}{2}\rfloor + \lfloor\frac{c'_3}{4}\rfloor + \dots + \lfloor\frac{c'_k}{2^{k - 1}}\rfloor $ . Note that some reindeer may contribute zero to the carrying capacity of the group. You have to process queries of three types: 1. add a reindeer with strength equal to $ 2^x $ to the herd; 2. remove a reindeer with strength equal to $ 2^x $ from the herd of reindeer; 3. calculate the number of ways to choose some of the reindeer from the herd (possibly all of them) so that the carrying capacity of the chosen group is at least $ x $ . If there are multiple reindeer with the same strength in the herd, they are considered different. For example, if you have two reindeer with strength $ 1 $ each, and you need to calculate the number of ways to choose a group with carrying capacity of at least $ 1 $ , there are $ 3 $ ways to choose it: choose the first reindeer, the second reindeer, or both of them.

The first line contains two integers $ n $ and $ m $ ( $ 1 \le n, m \le 3 \cdot 10^5 $ ) — the initial number of reindeer in the herd and the number of queries, respectively. The second line contains $ n $ integers $ c_1, c_2, \dots, c_n $ ( $ 0 \le c_i \le 60 $ ) denoting the strengths of the reindeer in the herd: the strength of the $ i $ -th reindeer is $ 2^{c_i} $ . The next $ m $ lines describe the queries in one of the following formats: - $ 1 $ $ x $ ( $ 0 \le x \le 60 $ ) — add a reindeer with strength equal to $ 2^x $ to the herd; - $ 2 $ $ x $ ( $ 0 \le x \le 60 $ ) — remove a reindeer with strength equal to $ 2^x $ from the herd; - $ 3 $ $ x $ ( $ 1 \le x \le 10^{18} $ ) — calculate the number of ways to choose a group of reindeer from the herd so that the carrying capacity of the chosen group is at least $ x $ . Additional constraint on the input: whenever a query of type $ 2 $ is given, the herd currently contains at least one reindeer with strength equal to $ 2^x $ .

For each query of the third type, print a single integer — the number of ways to choose a group of reindeer from the herd (possibly the whole herd) so that the carrying capacity of the chosen group is at least $ x $ . Since it can be huge, print it modulo $ 998244353 $ .

Let's consider the first example. Initially, there are three reindeer with strength equal to $ 4 $ , $ 2 $ and $ 2 $ , respectively. - during the first query, you have to calculate the number of ways to choose a group with carrying capacity of at least $ 5 $ . There are three possible groups: $ \{1, 2\} $ (the group containing the $ 1 $ -st and the $ 2 $ -nd reindeer), $ \{1, 2, 3\} $ , and $ \{1, 3\} $ ; - during the second query, you have to calculate the number of ways to choose a group with carrying capacity of at least $ 6 $ . Even the whole herd has carrying capacity equal to $ 4 + \lfloor\frac{2}{2}\rfloor + \lfloor\frac{2}{4}\rfloor = 5 $ , so there are no suitable ways to choose a group; - during the third query, a reindeer with strength $ 4 $ is added. Let's denote it as the $ 4 $ -th reindeer; - during the fourth query, the possible groups are $ \{1, 4\} $ , $ \{1, 2, 4\} $ , $ \{1, 3, 4\} $ and $ \{1, 2, 3, 4\} $ ; - during the fifth query, there are $ 10 $ possible groups; - during the sixth query, a reindeer with strength $ 2 $ is removed. Let's say that it was the $ 2 $ -nd reindeer, so only reindeer $ 1, 3, 4 $ remain; - during the seventh query, you have to calculate the number of ways to choose a group with carrying capacity of at least $ 5 $ . There are four possible groups: $ \{1, 3\} $ , $ \{1, 4\} $ , $ \{1, 3, 4\} $ , $ \{3, 4\} $ .