题目描述

千羽是个可爱的女孩子，她在序列王国收到了人们送给她的一些区间。千羽对这些区间产生了很大的兴趣，她希望聪明的你能给予她一些帮助。

给出 n 个数轴上的区间 [li,ri]（下标从 1 开始）。千羽定义 表示其中第 L 个到第 R 个的并覆盖了数轴上多长。

千羽会像你发出 q 次询问，每次给出 ql, qr。请你求出：如果我们从 [ql, qr] 中，等概率随机选择一个子区间 [L,R]，那么得到的 w(L, R) 的期望会是多少。

答案对 998244353 取模。

输入格式

第一行两个整数 n, q。 接下来 n 行，每行两个整数 li, ri。 接下来 q 行，每行两个整数 ql, qr。

输出格式

q 行，每行一个整数表示答案对 998244353 取模的结果。

样例输入1

2 1
1 5
4 8
1 2

样例输出1

5

样例输入2

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

样例输出2

0
4
499122189
9
11
332748129
4

样例输入3

15 9
910 910
600 630
910 910
60 740
570 580
60 800
260 910
910 910
670 910
450 470
590 610
60 260
800 910
60 260
260 260
7 10
1 3
8 11
5 15
3 13
6 10
2 10
11 13
9 12

样例输出3

362
20
164
574747259
604997180
332748635
665496868
332748316
200

数据范围

对于所有数据 1 <= n <= 8 x 10 ^ 5。1 <= q <= 2 x 10 ^ 6，0 <= li <= ri < 998244353, 1 <= ql <= qr <= n。

对于测试点 1-2：n, q <= 100

对于测试点 3-4：n, q <= 1000

对于测试点 5：n, q <= 5000

对于测试点 6-8：n <= 1000, q <= 100000

对于测试点 9-10：n <= 100000, q <= 1

对于测试点 11-15：n, q <= 100000

对于测试点 16-18：n, q <= 500000

对于测试点 19-20: 无特殊性质。

测试点等分。