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

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

Теперь Маленький Джон богат, и поэтому он наконец-то покупает дом, достаточно большой, чтобы вместить его и его любимую скобочную последовательность. Но каким-то образом он оказался с большим количеством скобок! Разочарованный, он пробивает потолок с помощью «ладони Будды».

Скобочная последовательность называется правильной, если она может быть построена по следующей формальной грамматике:

  1. Пустая последовательность $$$\varnothing$$$ сбалансирована.
  2. Если скобочная последовательность $$$A$$$ правильная, то $$$\mathtt{(}A\mathtt{)}$$$ также является правильной.
  3. Если скобочные последовательности $$$A$$$ и $$$B$$$ правильные, то и их конкатенированная последовательность $$$A B$$$ также правильная.

Например, последовательности «(())()», «()», «(()(()))» и пустая последовательность являются правильными, в то время как «(()» и «(()))(» — нет.

Дана правильная скобочная последовательность $$$s$$$, пара индексов $$$(i,j)$$$ ($$$i<j$$$) называется хорошей, если $$$s_i$$$ — это «(», а $$$s_j$$$ — это «)», и две скобки добавляются одновременно в соответствии с правилом 2 при построении последовательности $$$s$$$. Например, последовательность «(())()» имеет три разные хорошие пары: $$$(1,4)$$$, $$$(2,3)$$$ и $$$(5,6)$$$. Можно показать, что любая правильная скобочная последовательность из $$$2n$$$ скобок содержит ровно $$$n$$$ различных пар скобок, и использование любого порядка правил для построения одной и той же последовательности скобок приведет к одному и тому же набору пар скобок.

Эмили будет играть в игру по угадыванию скобок с Джоном. Игра проходит следующим образом.

Изначально у Джона есть правильная скобочная последовательность $$$s$$$, содержащая $$$n$$$ различных пар скобок, которая не известна Эмили. Джон говорит Эмили значение $$$n$$$ и просит Эмили угадать последовательность.

На протяжении $$$n$$$ ходов Джон дает Эмили следующие подсказки на каждом ходе:

  • $$$l\;r$$$: Последовательность $$$s$$$ содержит пару скобок $$$(l,r)$$$.

Гарантируется, что подсказки, которые Джон дает Эмили, попарно различны и не противоречат друг другу.

В какой-то момент Эмили может быть уверена, что правильная скобочная последовательность, удовлетворяющая подсказкам, данным до сих пор, уникальна. Например, предположим, что Эмили знает, что $$$s$$$ имеет $$$3$$$ хорошие пары, и она содержит пару скобок $$$(2,5)$$$. Из $$$5$$$ правильных скобочных последовательностей с $$$3$$$ хорошими парами существует только одна такая последовательность «((()))» с парой скобок $$$(2,5)$$$. Следовательно, можно увидеть, что Эмили не всегда нужно $$$n$$$ ходов, чтобы угадать $$$s$$$.

Чтобы как можно раньше узнать содержимое $$$s$$$, Эмили хочет знать количество различных правильных скобочных последовательностей, которые соответствуют подсказкам после каждого хода. Конечно, это не легкая задача для Эмили, особенно когда ей дано настолько много хороших пар. Теперь ваша очередь помочь Эмили. Учитывая подсказки, вы должны найти ответ до всех ходов и после каждого хода. Поскольку ответы могут быть огромными, вам нужно найти их по модулю $$$998\,244\,353$$$.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$) — количество хороших пар.

Затем каждая из следующих $$$n$$$ строк содержит два целых числа $$$l_i$$$ и $$$r_i$$$, представляющих $$$i$$$-ю подсказку ($$$1 \le l_i < r_i \le 2n$$$).

Подсказки в одном наборе входных данных попарно различны и не противоречат друг другу.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$3 \cdot 10^5$$$.

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

Для каждого набора выведите $$$n+1$$$ целых числа в одной строке:

  • Первое целое число — это ответ до всех подсказок, по модулю $$$998\,244\,353$$$.
  • Для всех $$$i \ge 1$$$, $$$i+1$$$-е целое число — это ответ после $$$i$$$-й подсказки, по модулю $$$998\,244\,353$$$.
Пример
Входные данные
3
3
2 5
1 6
3 4
4
1 6
7 8
2 3
4 5
6
2 3
1 6
7 8
9 12
10 11
4 5
Выходные данные
5 1 1 1
14 2 2 1 1
132 42 5 2 1 1 1
Примечание

Первый пример из примера объясняется в описании задачи.

Третий пример из примера объясняется следующим образом.

Можно показать, что существует $$$132$$$ сбалансированных последовательностей скобок с $$$6$$$ парами скобок. Ответы после каждой подсказки следующие:

  1. Вам дана хорошая пара $$$(2,3)$$$. Существует $$$42$$$ правильных скобочных последовательностей, имеющих хорошую пару $$$(2,3)$$$.
  2. Вам дана хорошая пара $$$(1,6)$$$. Существует $$$5$$$ правильных скобочных последовательностей, имеющих хорошие пары $$$(2,3)$$$, $$$(1,6)$$$.
  3. Вам дана хорошая пара $$$(7,8)$$$. Существуют $$$2$$$ правильных скобочных последовательностей, имеющих три хорошие пары. Это строки «(()())()(())» и «(()())()()()», соответственно.
  4. Вам дана хорошая пара $$$(9,12)$$$. Существует только одна правильная скобочная последовательность, содержащая четыре хорошие пары. Таким образом, содержимое $$$s$$$ имеет вид «(()())()(())».

Тогда количество правильных скобочных последовательностей после пятой и шестой подсказки равно $$$1$$$, поскольку вы уже знаете содержимое $$$s$$$.