CF2063F2.Counting Is Not Fun (Hard Version)

这是该问题的困难版本。与简单版本的区别在于，此版本对 $t$ 和 $n$ 的限制更大。仅当解决所有版本的问题时方可进行 hack。

小 John 现在很富有，终于买得起能容纳自己和最喜爱括号序列的大房子了。但不知为何，他得到了大量括号！沮丧之下，他用"佛掌"击穿了天花板。一个括号序列被称为平衡的，当且仅当其可以通过以下形式文法构造：

1. 空序列 $\varnothing$ 是平衡的。
2. 若括号序列 $A$ 是平衡的，则 $\mathtt{(}A\mathtt{)}$ 也是平衡的。
3. 若括号序列 $A$ 和 $B$ 是平衡的，则拼接序列 $AB$ 也是平衡的。

例如，序列 "(())()"、"()"、"(()(()))" 和空序列是平衡的，而 "(()" 和 "(()))(" 则不是。

给定一个平衡括号序列 $s$，当满足以下条件时，索引对 $(i,j)$（$i<j$）被称为好对：$s_i$ 是 '('，$s_j$ 是 ')'，且这两个括号是在构造序列 $s$ 时通过规则 2 同时添加的。例如，序列 "(())()" 有三个不同的好对：$(1,4)$、$(2,3)$ 和 $(5,6)$。可以证明，任何包含 $2n$ 个括号的平衡括号序列恰好有 $n$ 个不同的好对，且无论用何种规则顺序构造同一括号序列，得到的好对集合都相同。

Emily 将与 John 进行括号猜谜游戏。游戏规则如下：

初始时，John 有一个包含 $n$ 个不同好对的平衡括号序列 $s$，但 Emily 不知道其内容。John 告诉 Emily $n$ 的值，并要求 Emily 猜测该序列。

在 $n$ 轮中，John 每轮给出如下形式的线索：

• $l\;r$：序列 $s$ 包含好对 $(l,r)$。

John 给出的线索互不相同且互不矛盾。

在某个时刻，Emily 可以确定满足当前所有线索的平衡括号序列是唯一的。例如，假设 Emily 知道 $s$ 有 $3$ 个好对，并包含好对 $(2,5)$。在 $5$ 个有 $3$ 个好对的平衡括号序列中，只有序列 "((()))" 包含好对 $(2,5)$。因此，可以看出 Emily 并不总是需要 $n$ 轮才能猜出 $s$。

为了尽早确定 $s$ 的内容，Emily 希望知道每轮线索后符合条件的平衡括号序列数量。显然这对 Emily 来说并非易事，尤其当存在大量好对时。现在轮到你来帮助 Emily。给定所有线索，你需要在每轮前后输出答案。由于答案可能很大，请对 $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$ 取模。

样例中的第一个测试用例已在题目描述中解释。

第三个测试用例的解释如下：可以证明存在 $132$ 个有 $6$ 个好对的平衡括号序列。每接收一条线索后的答案如下：

1. 收到好对 $(2,3)$ 后，存在 $42$ 个符合条件的序列。
2. 收到好对 $(1,6)$ 后，存在 $5$ 个同时包含 $(2,3)$ 和 $(1,6)$ 的序列。
3. 收到好对 $(7,8)$ 后，存在 $2$ 个满足三个好对的序列，分别为 "(()())()(())" 和 "(()())()()()"。
4. 收到好对 $(9,12)$ 后，仅剩 $1$ 个满足四个好对的序列，即 "(()())()(())"。
   之后的第五、第六条线索接收后答案均为 $1$，因为此时已确定唯一序列。

翻译由 DeepSeek R1 完成