Minimizing Variance with Constrained Intervals

You are given an integer n and q queries. In addition, you are given n intervals \([l_i, r_i]\) (1-indexed) with l_i and r_i being positive integers. For each query, an integer x is provided. Your task is to choose an integer a_i from each interval (i.e. \(l_i \le a_i \le r_i\)) such that the total sum \(\sum_{i=1}^{n} a_i = x\) and the variance of the sequence \(a = (a_1,a_2,\ldots,a_n)\) is minimized.

The variance is defined as follows:

[ \mathrm{Var}(a) = \frac{1}{n}\sum_{i=1}^{n}a_i^2 - \Bigl(\frac{1}{n}\sum_{i=1}^{n}a_i\Bigr)^2 = \frac{1}{n}\sum_{i=1}^{n}a_i^2 - \Bigl(\frac{x}{n}\Bigr)^2. ]

You should output the minimum possible variance modulo \(998\,244\,353\). Note that the answer is a rational number. You are required to output it according to the convention of rational numbers modulo \(998\,244\,353\) (see standard templates such as [Template: Rational Number Modulo]).

Hint: Since \(\frac{x}{n}\) is fixed, minimizing the variance is equivalent to minimizing \(\sum_{i=1}^{n}a_i^2\). The optimal strategy is to start by taking the lower bound \(l_i\) from each interval, and then distribute the remaining \(D=x-\sum_{i=1}^{n}l_i\) units among the intervals as evenly as possible (without exceeding \(r_i\)). In each step, increasing the smallest current value minimizes the increase in the sum of squares, because the incremental cost of increasing \(a_i\) by 1 is \(2a_i+1\).

inputFormat

The first line contains two integers \(n\) and \(q\) separated by a space.

Then \(n\) lines follow. The i-th of these lines contains two integers \(l_i\) and \(r_i\) representing the interval \([l_i, r_i]\).

After that, \(q\) lines follow. Each of these lines contains one integer \(x\) representing a query. It is guaranteed that \(x\) is such that there exists at least one sequence \(a\) with \(a_i \in [l_i,r_i]\) and \(\sum_{i=1}^{n}a_i=x\).

outputFormat

For each query, output one line containing the minimum possible variance modulo \(998\,244\,353\). Recall that if the answer is a rational number \(\frac{P}{Q}\), you should output \(P \cdot Q^{-1} \bmod 998\,244\,353\), where \(Q^{-1}\) is the modular inverse of \(Q\) modulo \(998\,244\,353\).

sample

3 1
1 3
2 4
3 5
10

887328314