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

Input

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.

Output

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

Note

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.