Background

Original problem link: https://oier.team/problems/X3E。

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

Problem Description

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. For taking a rational number modulo, refer to [Template] Rational Modulo。

Input Format

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 Format

Output $q$ lines, each containing one integer: the minimum variance modulo $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

Hint

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.

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