Назовем увеличением дроби $$$\frac{x}{y}$$$ одну из следующих операций:
Обратите внимание, что после увеличения дробь не сокращается. Например, если изначально есть дробь $$$\frac{3}{7}$$$, и ее знаменатель уменьшается на $$$1$$$, мы получаем $$$\frac{3}{6}$$$, а не $$$\frac{1}{2}$$$.
Пусть вам задан массив целых чисел $$$b_1, b_2, \dots, b_m$$$ и целое число $$$k$$$. Вы применяете на него следующий алгоритм:
Назовем $$$\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 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}$$$.
