Statement : Sum of Fractions

An increase of the fraction $\frac{x}{y}$ is one of:

• increase the numerator $x$ by $1$, or
• if $y > 1$, decrease the denominator $y$ by $1$.

The fraction is not reduced after an increase (e.g. $\frac{3}{7} \to \frac{3}{6}$, not $\frac{1}{2}$).

Given an array $b_1, b_2, \ldots, b_m$ and an integer $k$, consider:

1. Build fractions $\frac{1}{b_1}, \frac{1}{b_2}, \ldots, \frac{1}{b_m}$.
2. Choose any fraction and apply an increase to it.
3. Repeat step 2 exactly $k$ times (same fraction can be chosen multiple times).
4. Take the sum of the resulting fractions.

Define $\mathrm{MSF}(b, k)$ as the maximum sum achievable over $b$ with exactly $k$ increases.

Let $a[l \ldots r]$ denote the subarray $a_l, a_{l+1}, \ldots, a_r$.

You are given arrays $a_1, \ldots, a_n$ and $k_1, k_2, \ldots, k_m$. For each $k_i$, compute

Output each result as $P \cdot Q^{-1} \bmod 998\,244\,353$ (standard modular inverse form).

First line: two integers $n$ and $m$ ($1 \le n, m \le 5 \cdot 10^5$).

Second line: $n$ integers $a_1, \ldots, a_n$ ($1 \le a_i \le 10^8$).

Third line: $m$ integers $k_1 \le k_2 \le \cdots \le k_m$ ($0 \le k_i \le 10^8$).

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

Input

5 4
2 3 5 2 3
0 1 2 10

Output

232923695
332748137
931694761
133099397

Note

The answers as rationals are $\frac{379}{30}$, $\frac{58}{3}$, $\frac{473}{15}$, $\frac{2249}{15}$.