F2. Фокусник и свиньи (сложная версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Единственное различие между двумя версиями  — это ограничения на $$$n$$$ и $$$x$$$. Вы можете делать взломы, только если обе версии задачи решены.

Little09 давно интересуется магией, и как же ему повезло, что он встречает фокусника! Фокусник выполнит $$$n$$$ операций, каждая из которых является одной из следующих трех:

  • $$$1\ x$$$: Создать свинью с $$$x$$$ очками здоровья.
  • $$$2\ x$$$: Уменьшить очки здоровья всех живых свиней на $$$x$$$.
  • $$$3$$$: Повторить все предыдущие операции. Формально, предполагая, что это $$$i$$$-я операция в последовательности операций, выполните по очереди первые $$$i-1$$$ операций (включая операции «Повторить»).

Свинья умирает, когда ее очки здоровья становятся меньше или равны $$$0$$$.

Little09 хочет знать, сколько живых свиней осталось после всех операций. Пожалуйста, выведите ответ по модулю $$$998\,244\,353$$$.

Входные данные

Первая строка содержит одно целое число $$$n$$$ ($$$1\leq n\leq 8\cdot 10^5$$$)  — количество операций.

Каждая из следующих $$$n$$$ строк содержит операцию, заданную в форме, описанной в условии задачи. Гарантируется, что $$$1\leq x\leq 10^9$$$ в операциях первых двух типов.

Выходные данные

Выведите одно целое число  — количество живых свиней после всех операций, по модулю $$$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
Примечание

В первом примере операции эквивалентны повторению следующего четыре раза: создать свинью с $$$8$$$ очками здоровья, а затем уменьшить очки здоровья всех живых свиней на $$$3$$$. Легко видеть, что в конце остаются две живые свиньи с $$$2$$$ и $$$5$$$ очками здоровья.