| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 4 초 | 512 MB | 2 | 2 | 2 | 100.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$.
2 1 1 5 4 8 1 2
5
The size of input and output is large. Remember to use fast input and output methods to avoid getting a "Time Limit Exceeded".