Segment Covering

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

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$ 的值，这样他就不会让她失望了。

输入格式

输入的第一行包含两个整数 $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 < y_i \leq 10^9$），表示一条线段 $[x_i, y_i]$。

保证所有线段互不相同。更正式地说，不存在 $1 \leq i < j \leq m$ 使得 $x_i = x_j$ 且 $y_i = y_j$。

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

输出格式

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

样例输入 1

4 2
1 3
4 6
2 4
3 5
1 4
1 5

样例输出 1

1
0

提示

在第一个询问中，我们需要计算 $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$。

数据范围

对于所有数据，$1\le m,q\le2\times10^5$，$1\le x_i<y_i\le10^9$，$1\le l_i<r_i\le10^9$，且输入线段两两不同。

每个测试点独立计分。