← 返回题目列表

Codeforces · 1774/G

G. 段覆盖

中文机器翻译题面 查看原题

ChthollyNotaSeniorious 为 DataStructures 提供了一个数字轴,其上有 $$$m$$$ 不同的段。设 $$$f(l,r)$$$ 为选择偶数段的方法数,使得它们的并集恰好为 $$$[l,r]$$$,$$$g(l,r)$$$ 为选择奇数段的方法数,使得它们的并集恰好为 $$$[l,r]$$$。

ChthollyNotaSeniorious 问了 DataStructures $$$q$$$ 问题。在每个查询中,ChthollyNotaSeniorious 都会给 DataStructures 两个数字 $$$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]$$$。

保证所有段都是不同的。更正式地说,不存在两个数字 $$$i, j$$$ 且 $$$1 \le i < j \le 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$$$。