F. Сумма дробей
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Назовем увеличением дроби $$$\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$$$. Вы применяете на него следующий алгоритм:

  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_l, a_{l + 1}, \dots a_r$$$ массива $$$a$$$.

Вам заданы два массива целых чисел $$$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 4
2 3 5 2 3
0 1 2 10
Выходные данные
232923695
332748137
931694761
133099397
Примечание

Ответы для соответствующих $$$k$$$ равны: $$$\frac{379}{30}$$$, $$$\frac{58}{3}$$$, $$$\frac{473}{15}$$$ и $$$\frac{2249}{15}$$$.