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: add a reindeer with strength equal to (2^x) to the herd; remove a reindeer with strength equal to (2^x) from the herd of reindeer; 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 o