410236: GYM103987 L Intervals

There are $$$n$$$ invervals, the $$$i$$$-th of which is $$$[l_i,r_i]$$$. We define the length covered by it as $$$r_i − l_i$$$.

Define the beauty of $$$[x, y]$$$ as the length covered by $$$\bigcup_{i=x}^y [l_i,r_i]$$$.

Now you are given m queries. For each query $$$[A,B]$$$, you need to find the expected beauty of $$$[x,y]$$$, where $$$[x,y]$$$ is uniformly sampled from all possible integer pairs such that $$$A \leq x \leq y \leq B$$$.

Find the answers modulo $$$998\ 244\ 353$$$.

The first line contains two integers $$$n$$$ ($$$1 \leq n \leq 2\cdot 10^5$$$) and $$$m$$$ ($$$1 \leq m \leq 2 \cdot 10^5$$$), the number of intervals and queries, respectively.

The following $$$n$$$ lines describe the intervals. The $$$i$$$-th line contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$0 \leq l_i < r_i \leq 10^8$$$).

The next $$$m$$$ lines describe the queries. The $$$i$$$-th line contains two integers $$$A_i$$$ and $$$B_i$$$ ($$$1 \leq A_i \leq B_i \leq n$$$)

For each query, print the answer in a line.

3 3
1 3
2 5
6 7
1 1
1 2
2 3

2
3
665496238

In the example above, there are $$$3$$$ intervals, $$$[1,3]$$$, $$$[2,5]$$$ and $$$[6,7]$$$.

In the first query, $$$x = y = 1$$$, so the answer is the beauty of $$$[1,1]$$$, equal to $$$3 − 1 = 2$$$.

In the second query, $$$[x,y]$$$ is randomly distributed in $$$\{[1,1],[1,2],[2,2]\}$$$. The beauty of them are $$$2$$$, $$$4$$$ and $$$3$$$, respectively, so the answer is $$$(2 + 4 + 3)/3 = 3$$$.

The answer to the third query is $$$(3 + 1 + 4)/3 = 8/3$$$.