시간 제한메모리 제한제출정답맞은 사람정답 비율
4 초 512 MB0000.000%

문제

You are given $n$ intervals, the $j$-th of which is $I_j = [l_j, r_j]$.

Define the beauty of $[L, R]$ as the length covered by $\displaystyle \bigcup\limits_{i = L}^R [l_i, r_i]$.

You are given $m$ queries, the $i$-th of which is $[A_i, B_i]$, and you need to answer:

If we uniformly sample $[L_i, R_i]$ from all possible integer pairs such that $A_i \le L_i \le R_i \le B_i$, what is the expected value of the beauty of $[L_i, R_i]$?

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

입력

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 2 \cdot 10^5$).

Each of the following $n$ lines contains two integers $l_j$ and $r_j$ ($0 \le l_j < r_j \le 10^8$).

Each of the following $m$ lines contains two integers $A_i$ and $B_i$ ($1 \le A_i \le B_i \le n$).

출력

Output $m$ lines, each of which contains the answer for a query modulo $998\,244\,353$.

Formally, it can be shown that the expected beauty can be represented as a fraction $p / q$ for some coprime non-negative integers $p$ and $q$. You have to print the value $p \cdot q^{-1} \bmod 998\,244\,353$.

예제 입력 1

2 1
1 5
4 8
1 2

예제 출력 1

5

노트

The size of input and output is large. Remember to use fast input and output methods to avoid getting a "Time Limit Exceeded".