B"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: 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 <= q n <= q 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 <= q x <= q 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 . 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. "...