CF2204F.Sum of Fractions

Let's call an increase of the fraction $\frac{x}{y}$ one of the following operations:

• either increase its numerator $x$ by $1$;
• or, if the denominator $y \gt 1$, decrease its denominator $y$ by $1$.

Note that the fraction is not reduced after the increase. For example, if you have a fraction $\frac{3}{7}$ and you decrease its denominator by $1$, you get $\frac{3}{6}$, not $\frac{1}{2}$.

Suppose you are given an integer array $b_1, b_2, \dots, b_m$ and an integer $k$. You apply the following algorithm:

1. Construct the array $\frac{1}{b_1}, \frac{1}{b_2}, \dots, \frac{1}{b_m}$.
2. Choose any of the fractions and increase it.
3. Repeat the previous step $k$ times (the same fraction can be chosen multiple times).
4. Calculate the sum of the resulting fractions.

We will denote $\mathrm{MSF}(b, k)$ as the maximum sum of fractions that can be obtained from the array $b$ by applying the increase operation exactly $k$ times.

Let $a[l \dots r]$ be the subarray $a_l, a_{l + 1}, \dots a_r$ of the array $a$.

You are given two arrays of integers $a_1, a_2, \dots, a_n$ and $k_1, k_2, \dots, k_m$. For each $k_i$, calculate $$\left( \sum\limits_{l = 1}^{n}{\sum\limits_{r = l}^{n}\mathrm{MSF}(a[l \dots r], k_i)} \right) \bmod 998\,244\,353.$$ In other words, for each $k_i$, calculate the sum of $\mathrm{MSF}$ over all subarrays of the array $a$ and output the answer modulo.

我们称对分数 $\frac{x}{y}$ 的“增加”为以下两种操作之一：

• 将其分子 $x$ 增加 $1$；
• 或者，若分母 $y > 1$，则将其分母 $y$ 减少 $1$。

注意：执行“增加”操作后，分数不约分。例如，若当前分数为 $\frac{3}{7}$，将其分母减 $1$ 后得到 $\frac{3}{6}$，而非 $\frac{1}{2}$。

现给定一个整数数组 $b_1, b_2, \dots, b_m$ 和一个整数 $k$。执行如下算法：

1. 构造数组 $\frac{1}{b_1}, \frac{1}{b_2}, \dots, \frac{1}{b_m}$。
2. 任选其中一个分数并对其执行一次“增加”操作。
3. 重复上一步 $k$ 次（同一分数可被多次选择）。
4. 计算最终所有分数的和。

我们将 $\mathrm{MSF}(b, k)$ 定义为：对数组 $b$ 恰好执行 $k$ 次“增加”操作所能得到的分数之和的最大值。

记 $a[l \dots r]$ 为数组 $a$ 的子数组 $a_l, a_{l + 1}, \dots, a_r$。

现给定两个整数数组 $a_1, a_2, \dots, a_n$ 和 $k_1, k_2, \dots, k_m$。对每个 $k_i$，计算

$$\left( \sum\limits_{l = 1}^{n}{\sum\limits_{r = l}^{n}\mathrm{MSF}(a[l \dots r], k_i)} \right) \bmod 998\,244\,353.$$

换言之，对每个 $k_i$，计算 $\mathrm{MSF}$ 在数组 $a$ 的所有子数组上的总和，并输出该结果对 $998\,244\,353$ 取模的值。

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 5 \cdot 10^5$) — the sizes of the arrays $a$ and $k$.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^8$) — the array $a$.

The third line contains $m$ integers $k_1, k_2, \dots, k_m$ ($0 \le k_1 \le k_2 \le \dots \le k_m \le 10^8$) — the array $k$ in non-decreasing order.

第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 5 \cdot 10^5$）—— 分别为数组 $a$ 和 $k$ 的长度。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^8$）—— 数组 $a$。

第三行包含 $m$ 个整数 $k_1, k_2, \dots, k_m$（$0 \le k_1 \le k_2 \le \dots \le k_m \le 10^8$）—— 按非递减顺序排列的数组 $k$。

For each $k_i$, output a single integer — the sum of $\mathrm{MSF}$ over all subarrays modulo $998\,244\,353$.

It can be proven that the answer can be represented as an irreducible fraction $\frac{P}{Q}$, where $Q \not\equiv 0 \pmod{998\,244\,353}$. Accordingly, output the answer in the form $P \cdot Q^{-1} \pmod{998\,244\,353}$.

对于每个 $k_i$，输出一个整数——即所有子数组的 $\mathrm{MSF}$ 之和对 $998\,244\,353$ 取模的结果。

可以证明，该答案可表示为既约分数 $\frac{P}{Q}$，其中 $Q \not\equiv 0 \pmod{998\,244\,353}$。因此，请以 $P \cdot Q^{-1} \pmod{998\,244\,353}$ 的形式输出答案。

The answers for the corresponding $k$ are: $\frac{379}{30}$, $\frac{58}{3}$, $\frac{473}{15}$, and $\frac{2249}{15}$.

对应 $k$ 的答案为：$\frac{379}{30}$、$\frac{58}{3}$、$\frac{473}{15}$ 和 $\frac{2249}{15}$。