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.

这是该问题的困难版本。两个版本的唯一区别在于 $n$ 和 $m$ 的上界。在本版本中，$n \le 3 \cdot 10^5$ 且 $m \le 3 \cdot 10^5$。

你有一群 $n$ 只圣诞驯鹿。第 $i$ 只驯鹿的力量为 $2^{c_i}$。

一组 $k$ 只圣诞驯鹿的承载能力按如下方式计算：

• 将这群驯鹿的力量按非递增顺序排序。记排序后的力量序列为 $c'_1, c'_2, \dots, c'_k$，其中 $c'_i \ge c'_{i+1}$；
• 则该组驯鹿的承载能力等于

$$c'_1 + \left\lfloor\frac{c'_2}{2}\right\rfloor + \left\lfloor\frac{c'_3}{4}\right\rfloor + \dots + \left\lfloor\frac{c'_k}{2^{k - 1}}\right\rfloor.$$

注意：某些驯鹿对群体承载能力的贡献可能为零。

你需要处理三种类型的查询：

1. 向驯鹿群中添加一只力量为 $2^x$ 的驯鹿；
2. 从驯鹿群中移除一只力量为 $2^x$ 的驯鹿；
3. 计算从当前驯鹿群中选出若干只驯鹿（可以全选，也可以不选）的方式数，使得所选群体的承载能力至少为 $x$。

若驯鹿群中存在多只力量相同的驯鹿，则它们被视为互不相同。例如，若你有两只力量均为 $1$ 的驯鹿，而你需要计算承载能力至少为 $1$ 的选择方案数，则共有 $3$ 种方案：仅选第一只、仅选第二只，或同时选两只。

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$.

第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 3 \cdot 10^5$），分别表示鹿群中初始的驯鹿数量以及查询次数。

第二行包含 $n$ 个整数 $c_1, c_2, \dots, c_n$（$0 \le c_i \le 60$），表示鹿群中各驯鹿的力量值：第 $i$ 只驯鹿的力量为 $2^{c_i}$。

接下来的 $m$ 行描述了 $m$ 个查询，每个查询为以下格式之一：

• $1$ $x$（$0 \le x \le 60$）——向鹿群中添加一只力量为 $2^x$ 的驯鹿；
• $2$ $x$（$0 \le x \le 60$）——从鹿群中移除一只力量为 $2^x$ 的驯鹿；
• $3$ $x$（$1 \le x \le 10^{18}$）——计算从当前鹿群中选出一组驯鹿的方式数，使得该组驯鹿的总承载能力至少为 $x$。

输入附加约束：每当出现类型为 $2$ 的查询时，鹿群中当前至少存在一只力量为 $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$.

对于每个第三种类型的查询，输出一个整数——即从驯鹿群中（可能选择整个驯鹿群）选出一组驯鹿，使得该组驯鹿的承载能力至少为 $x$ 的方案数。由于结果可能非常大，请对 $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}$.

我们来考虑第一个例子。初始时有三只驯鹿，其力量值分别为 $4$、$2$ 和 $2$。

• 在第一次查询中，你需要计算选出一个承载能力至少为 $5$ 的群体的方法数。共有三种可能的群体：${1, 2}$（包含第 $1$ 只和第 $2$ 只驯鹿的群体）、${1, 2, 3}$ 和 ${1, 3}$；
• 在第二次查询中，你需要计算选出一个承载能力至少为 $6$ 的群体的方法数。即使整个鹿群的承载能力也仅为 $4 + \lfloor\frac{2}{2}\rfloor + \lfloor\frac{2}{4}\rfloor = 5$，因此不存在满足条件的群体；
• 在第三次查询中，加入一只力量值为 $4$ 的驯鹿；我们将其记作第 $4$ 只驯鹿；
• 在第四次查询中，可能的群体有 ${1, 4}$、${1, 2, 4}$、${1, 3, 4}$ 和 ${1, 2, 3, 4}$；
• 在第五次查询中，共有 $10$ 种可能的群体；
• 在第六次查询中，移除一只力量值为 $2$ 的驯鹿；假设被移除的是第 $2$ 只驯鹿，则剩余驯鹿为第 $1$、$3$、$4$ 只；
• 在第七次查询中，你需要计算选出一个承载能力至少为 $5$ 的群体的方法数。共有四种可能的群体：${1, 3}$、${1, 4}$、${1, 3, 4}$、${3, 4}$。