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,\dots ,b_m$ and an integer $k$, consider:

1. Build fractions $\frac{1}{b_1},\frac{1}{b_2},\dots ,\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\dots r]$ denote the subarray $a_l,a_{l+1},\dots ,a_r$.

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

$$(\sum _{l=1}^n\sum _{r=l}^n\mathrm{MSF}(a[l\dots r],k_i))mod998,244,353.$$

Output each result as $P\cdot Q^{-1}mod998,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,\dots ,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}$.