题目描述

对于一个由区间构成的序列 $a=([l_1,r_1],\dots,[l_n,r_n])$，定义 $a$ 的宽度为最小的非负整数 $k$，使得：

• 存在一个由区间构成的序列 $b=([s_1,t_1],\dots,[s_n,t_n])$，满足：
  • 对于所有 $1\le i\le n$，有 $1\le s_i\le t_i\le k$。
    • 对于所有 $1\le i < j\le n$，有 $[l_i,r_i]\cap [l_j,r_j] \neq \varnothing \iff [s_i,t_i]\cap [s_j,t_j] \neq \varnothing$，即 “$[l_i,r_i]$ 与 $[l_j,r_j]$ 相交”“$[s_i,t_i]$ 与 $[s_j,t_j]$ 相交”要么同时成立，要么同时不成立。

特别地，空序列的宽度为 $0$。

给定长度为 $n$ 的序列 $c$，你需要处理 $q$ 次询问。每次询问给定参数 $x,y\ (x\le y)$，然后按照以下方式计算出序列 $a$：

• 初始序列 $a$ 为空。
• 对于 $c$ 中的每个元素 $[l_i,r_i]$，依次执行：
  • 若 $r_i < x$ 或 $l_i > y$，什么都不做；
    • 否则，在序列 $a$ 的末尾添加一个元素 $[\max\{l_i,x\},\min\{r_i,y\}]$。

你需要对序列 $a$，求出以下问题的答案：

• 对于 $a$ 的所有 $2^{|a|}$ 个子序列，计算它们的宽度，求这 $2^{|a|}$ 个宽度的和。

注意序列 $a$ 中相同的元素在选取子序列时被视作本质不同的。

例如，若 $a=([1,1],[2,3],[2,3])$，则 $a$ 的 $8$ 个子序列为：$\varnothing,([1,1]),([2,3]),([1,1,2,3]), ([2,3]),([1,1],[2,3]),([2,3],[2,3]),([1,1],[2,3],[2,3])$。

答案对 $998244353$ 取模。

输入格式

第一行包含两个正整数 $n,q$。

接下来 $n$ 行，每行包含两个正整数 $l_i,r_i$，表示序列 $c$ 的第 $i$ 个元素 $c_i=[l_i,r_i]$。

接下来 $q$ 行，每行包含两个正整数 $x_i,y_i$，表示一次询问。

输出格式

输出 $q$ 行，每行一个非负整数，表示询问的答案对 $998244353$ 取模的结果。

输入样例1

5 2
1 1
1 2
2 2
2 3
1 2
2 3
1 3

输出样例1

15
43

explanation

一些子序列的宽度：

• $([1,1],[1,2])$：宽度为 $1$，可以选取 $b=([1,1],[1,1])$。
• $([1,1],[2,2])$：宽度为 $2$，可以选取 $b=([1,1],[2,2])$。
• $([1,1],[1,2],[2,3])$：宽度为 $2$，可以选取 $b=([1,1],[1,2],[2,2])$。

输入样例2

20 5
4 5 3 8 1 3 3 9 1 6 2 9 1 1 1 9 1 2 3 6 2 2 3 3 5 8 1 2 2 7 4 5 2 5 3 6 6 9 3 7
5 5
4 6
3 7
2 8
1 9

输出样例2

8191
23551
138751
1564847
3629339

explanation

为了压缩题面长度，部分换行被替换为了空格。下发文件中有格式正确的样例。

限制与约定

对于所有数据，保证 $1\le n,q\le 5\times 10^5$，$1\le l_i\le r_i\le 10^6$，$1\le x_i\le y_i\le 10^6$。

若 $q=1$，保证 $x_1\le l_i\le r_i\le y_1$，即计算出的 $a$ 等于 $c$。

特殊性质 $\texttt{A}$：保证不存在 $1\le i,j\le n,i\neq j$，使得 $l_i \le l_j \le r_i \le r_j$。

特殊性质 $\texttt{B}$：保证不存在 $1\le i,j\le n,i\neq j$，使得 $l_i \le l_j \le r_j \le r_i$。