CF1774G.Segment Covering

ChthollyNotaSeniorious gives DataStructures a number axis with $m$ distinct segments on it. Let $f(l,r)$ be the number of ways to choose an even number of segments such that the union of them is exactly $[l,r]$, and $g(l,r)$ be the number of ways to choose an odd number of segments such that the union of them is exactly $[l,r]$.

ChthollyNotaSeniorious asked DataStructures $q$ questions. In each query, ChthollyNotaSeniorious will give DataStructures two numbers $l, r$, and now he wishes that you can help him find the value $f(l,r)-g(l,r)$ modulo $998\,244\,353$ so that he wouldn't let her down.

ChthollyNotaSeniorious 给 DataStructures 一条数轴，其上有 $m$ 个互不相同的线段。定义 $f(l,r)$ 为：选出偶数个线段，使得它们的并集恰好等于区间 $[l,r]$ 的方案数；定义 $g(l,r)$ 为：选出奇数个线段，使得它们的并集恰好等于区间 $[l,r]$ 的方案数。

ChthollyNotaSeniorious 向 DataStructures 提出了 $q$ 个询问。每次询问中，ChthollyNotaSeniorious 会给出两个数 $l, r$，他希望你能帮他求出 $f(l,r)-g(l,r)$ 对 $998\,244\,353$ 取模的结果，以免让她失望。

The first line of input contains two integers $m$ ($1 \leq m \leq 2 \cdot 10^5$) and $q$ ($1 \leq q \leq 2 \cdot 10^5$) — the number of segments and queries, correspondingly.

The $i$-th of the next $m$ lines contains two integers $x_i$ and $y_i$ ($1 \leq x_i \lt y_i \leq 10^9$), denoting a segment $[x_i, y_i]$.

It is guaranteed that all segments are distinct. More formally, there do not exist two numbers $i, j$ with $1 \le i \lt j \le m$ such that $x_i = x_j$ and $y_i = y_j$.

The $i$-th of the next $q$ lines contains two integers $l_i$ and $r_i$ ($1 \leq l_i \lt r_i \leq 10^9$), describing a query.

输入的第一行包含两个整数 $m$（$1 \leq m \leq 2 \cdot 10^5$）和 $q$（$1 \leq q \leq 2 \cdot 10^5$），分别表示线段的数量和查询的数量。

接下来的 $m$ 行中，第 $i$ 行包含两个整数 $x_i$ 和 $y_i$（$1 \leq x_i \lt y_i \leq 10^9$），表示一条线段 $[x_i, y_i]$。

保证所有线段互不相同。更准确地说，不存在满足 $1 \le i \lt j \le m$ 的两个下标 $i, j$，使得 $x_i = x_j$ 且 $y_i = y_j$。

再接下来的 $q$ 行中，第 $i$ 行包含两个整数 $l_i$ 和 $r_i$（$1 \leq l_i \lt r_i \leq 10^9$），描述一次查询。

For each query, output a single integer — $f(l_i,r_i)-g(l_i,r_i)$ modulo $998\,244\,353$.

对于每个查询，输出一个整数 — $f(l_i,r_i)-g(l_i,r_i)$ 对 $998\,244\,353$ 取模的结果。

In the first query, we have to find $f(1, 4) - g(1, 4)$. The only subset of segments with union $[1, 4]$ is ${[1, 3], [2, 4]}$, so $f(1, 4) = 1, g(1, 4) = 0$.

In the second query, we have to find $f(1, 5) - g(1, 5)$. The only subsets of segments with union $[1, 5]$ are ${[1, 3], [2, 4], [3, 5]}$ and ${[1, 3], [3, 5]}$, so $f(1, 5) = 1, g(1, 5) = 1$.

在第一个查询中，我们需要计算 $f(1, 4) - g(1, 4)$。唯一满足并集为 $[1, 4]$ 的线段子集是 ${[1, 3], [2, 4]}$，因此 $f(1, 4) = 1,\ g(1, 4) = 0$。

在第二个查询中，我们需要计算 $f(1, 5) - g(1, 5)$。所有满足并集为 $[1, 5]$ 的线段子集为 ${[1, 3], [2, 4], [3, 5]}$ 和 ${[1, 3], [3, 5]}$，因此 $f(1, 5) = 1,\ g(1, 5) = 1$。