让我们调用 增加 分数的 $$$\frac{x}{y}$$$ 以下操作之一:
- 要么将其分子$$$x$$$增加$$$1$$$;
- 或者,如果分母 $$$y \gt 1$$$,则将其分母 $$$y$$$ 减少 $$$1$$$。
注意,增加后分数并没有减少。例如,如果您有一个分数 $$$\frac{3}{7}$$$,并将其分母减去 $$$1$$$,则得到 $$$\frac{3}{6}$$$,而不是 $$$\frac{1}{2}$$$。
假设给你一个整数数组 $$$b_1, b_2, \dots, b_m$$$ 和一个整数 $$$k$$$。您应用以下算法:
- 构造数组 $$$\frac{1}{b_1}、\frac{1}{b_2}、\dots、\frac{1}{b_m}$$$。
- 选择任意一个分数并增加它。
- 重复上一步 $$$k$$$ 次(可以多次选择相同的分数)。
- 计算所得分数的总和。
我们将 $$$\mathrm{MSF}(b, k)$$$ 表示为可以通过精确应用 $$$k$$$ 次增加运算从数组 $$$b$$$ 获得的最大分数和。
令 $$$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$$$ 的所有子数组并输出答案模数。
输入
第一行包含两个整数 $$$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$$$ 按非降序排列。
输出
对于每个 $$$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}$$$ 的形式输出答案。
示例
输入复制
5 42 3 5 2 30 1 2 10
输出复制
232923695 332748137 931694761 133099397
注意
相应 $$$k$$$ 的答案为:$$$\frac{379}{30}$$$、$$$\frac{58}{3}$$$、$$$\frac{473}{15}$$$ 和 $$$\frac{2249}{15}$$$。