Magician and Pigs (Hard Version)

你现在有一个空序列，需要维护如下三个操作： - $1\ x$：在序列中添加 $x$。 - $2\ x$：把序列中每个元素的值减去 $x$。 - $3$：重复从第一条到本条操作的前一条的所有操作。包括操作 $3$。 当一个数的值小于等于 $0$ 时，它将被移出序列。 请输出最后有多少个数还在序列中。答案对$998244353$ 取模。 输入格式： 第一行输入一个整数 $n(1\leq n \leq 8\times10^5)$，表示操作总数。 接下来的每行由操作名和 $x$ 构成（操作 $3$ 只有操作名）。其中 $1\leq x\leq 10^9$。

This is the hard version of the problem. The only difference between the two versions is the constraint on $ n $ and $ x $ . You can make hacks only if both versions of the problem are solved. Little09 has been interested in magic for a long time, and it's so lucky that he meets a magician! The magician will perform $ n $ operations, each of them is one of the following three: - $ 1\ x $ : Create a pig with $ x $ Health Points. - $ 2\ x $ : Reduce the Health Point of all living pigs by $ x $ . - $ 3 $ : Repeat all previous operations. Formally, assuming that this is the $ i $ -th operation in the operation sequence, perform the first $ i-1 $ operations (including "Repeat" operations involved) in turn. A pig will die when its Health Point is less than or equal to $ 0 $ . Little09 wants to know how many living pigs there are after all the operations. Please, print the answer modulo $ 998\,244\,353 $ .

The first line contains a single integer $ n $ ( $ 1\leq n\leq 8\cdot 10^5 $ ) — the number of operations. Each of the following $ n $ lines contains an operation given in the form described in the problem statement. It's guaranteed that $ 1\leq x\leq 10^9 $ in operations of the first two types.

Print a single integer — the number of living pigs after all the operations, modulo $ 998\,244\,353 $ .

4
1 8
2 3
3
3

2

6
1 5
1 6
2 2
3
1 4
3

5

12
2 1
1 15
1 9
3
1 12
2 2
1 13
3
2 1
1 9
1 8
3

17

In the first example, the operations are equivalent to repeating four times: create a pig with $ 8 $ Health Points and then reduce the Health Points of all living pigs by $ 3 $ . It is easy to find that there are two living pigs in the end with $ 2 $ and $ 5 $ Health Points.