【MX-X3-T4】「RiOI-4」上课

一天，小 M 在宿舍 $6:53$ 起床，而早自习 $7:00$ 开始。

给定正整数 $n,q$ 和 $n$ 个区间 $[l_i,r_i]$。 有 $q$ 组询问，每次询问给定一个整数 $x$。在每个区间内选择一个整数 $a_i$（$l_i\leq a_i\leq r_i$），使得所选整数的总和等于 $x$，并使得选出的 $a$ 序列的方差最小。输出方差最小值，对 $998\,244\,353$ 取模。保证存在至少一种合法的选取方案。 关于方差的有关定义参照此[云剪切板](https://www.luogu.com.cn/paste/dpptrubn)，有理数取模参照[【模板】有理数取余](https://www.luogu.com.cn/problem/P2613)。

第一行两个正整数 $n,q$。 接下来的 $n$ 行，每行两个自然数 $l_i,r_i$。 最后 $q$ 行，每行一个整数 $x$，表示一次询问。保证存在至少一种合法的选取方案。

$q$ 行，每行一个整数，表示最小方差对 $998\,244\,353$ 取模的值。

3 3
1 3
2 3
3 5
6
9
11

665496236
0
554580197

4 3
1 4
11 12
3 9
6 10
21
29
26

811073551
811073543
748683272

**【样例解释 #1】** 询问一方差最小的选择方案为 ${1,2,3}$，最小方差为 $\frac{2}{3}$，有 $665\,496\,236\times3\equiv 2\pmod{998\,244\,353}$，故输出 $665\,496\,236$。 询问二方差最小的选择方案为 ${3,3,3}$，最小方差为 $0$，有 $0\times1\equiv 0\pmod {998\,244\,353}$，故输出 $0$。 询问三方差最小的选择方案为 ${3,3,5}$，最小方差为 $\frac{8}{9}$，有 $554\,580\,197\times9\equiv 8\pmod{998\,244\,353}$，故输出 $554\,580\,197$。 **【数据范围】** **本题开启捆绑测试。** |子任务|分数|$n$|$q$|特殊性质| |:-:|:-:|:-:|:-:|:-:| |$1$|$9$|$\le5$|$\le5$|$r_i\le5$| |$2$|$13$|$\le2\times10^3$|$\le2\times10^3$|$r_i\le2\times10^3$| |$3$|$16$|$\le10^6$|$=1$|| |$4$|$25$|$\le10^5$|$\le10^5$|$r_i\le10^5$| |$5$|$37$|$\le10^6$|$\le10^6$|| 对于所有数据，满足 $1\leq n,q\leq 10^6$，$0\leq l_i\leq r_i\leq 10^{6}$，对于每个 $x$ 保证存在一种合法的方案。