P11037 [MX-X3-T4] "RiOI-4" Attending Class

Original problem link: 。 --- One day, Little M got up in the dorm at $6:53$, and the morning self-study starts at $7:00$。

Given positive integers $n, q$ and $n$ intervals $[l_i, r_i]$。 There are $q$ queries. In each query, an integer $x$ is given. Choose an integer $a_i$ in each interval ($l_i \leq a_i \leq r_i$), so that the sum of all chosen integers equals $x$, and the variance of the chosen sequence $a$ is minimized. Output the minimum variance modulo $998\,244\,353$. It is guaranteed that there is at least one valid selection. For the definition of variance, refer to this [Luogu paste](https://www.luogu.com.cn/paste/dpptrubn). For taking a rational number modulo, refer to [[Template] Rational Modulo](https://www.luogu.com.cn/problem/P2613)。

The first line contains two positive integers $n, q$。 The next $n$ lines each contain two natural numbers $l_i, r_i$。 The last $q$ lines each contain an integer $x$, representing one query. It is guaranteed that there exists at least one valid selection。

Output $q$ lines, each containing one integer: the minimum variance modulo $998\,244\,353$。

**Sample Explanation #1** For query 1, a selection with minimum variance is ${1,2,3}$. The minimum variance is $\frac{2}{3}$. Since $665\,496\,236 \times 3 \equiv 2 \pmod{998\,244\,353}$, output $665\,496\,236$。 For query 2, a selection with minimum variance is ${3,3,3}$. The minimum variance is $0$. Since $0 \times 1 \equiv 0 \pmod{998\,244\,353}$, output $0$。 For query 3, a selection with minimum variance is ${3,3,5}$. The minimum variance is $\frac{8}{9}$. Since $554\,580\,197 \times 9 \equiv 8 \pmod{998\,244\,353}$, output $554\,580\,197$。 **Constraints** **This problem uses bundled testdata.** |Subtask|Score|$n$|$q$|Special Property| |:-:|:-:|:-:|:-:|:-:| |$1$|$9$|$\le 5$|$\le 5$|$r_i \le 5$| |$2$|$13$|$\le 2\times 10^3$|$\le 2\times 10^3$|$r_i \le 2\times 10^3$| |$3$|$16$|$\le 10^6$|$= 1$|| |$4$|$25$|$\le 10^5$|$\le 10^5$|$r_i \le 10^5$| |$5$|$37$|$\le 10^6$|$\le 10^6$|| For all testdata, $1 \leq n, q \leq 10^6$, $0 \leq l_i \leq r_i \leq 10^6$. For each $x$, it is guaranteed that there exists a valid selection. Translated by ChatGPT 5