题目背景

一天，小 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$ 取模。保证存在至少一种合法的选取方案。

关于方差的有关定义参照此云剪切板，有理数取模参照【模板】有理数取余。

输入格式

第一行两个正整数 $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$。

【数据范围】

本题开启捆绑测试。

对于所有数据，满足 $1\leq n,q\leq 10^6$，$0\leq l_i\leq r_i\leq 10^{6}$，对于每个 $x$ 保证存在一种合法的方案。