В ряд расположено $$$n$$$ мешков, пронумерованных от $$$1$$$ до $$$n$$$; $$$i$$$-й мешок содержит $$$a_i$$$ золотых монет и $$$b_i$$$ серебряных монет.
Ценность золотой монеты равна $$$1$$$. Ценность серебряной монеты равна $$$0$$$ или $$$1$$$, и определяется для каждой серебряной монеты независимо ($$$0$$$ с вероятностью $$$\frac{1}{2}$$$ и $$$1$$$ с вероятностью $$$\frac{1}{2}$$$).
Вам нужно ответить на $$$q$$$ независимых запросов. Каждый запрос имеет следующий формат:
Первая строка содержит два целых числа $$$n$$$ и $$$q$$$ ($$$1 \le n, q \le 3 \cdot 10^5$$$) — количество мешков и количество запросов, соответственно.
Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^6$$$) — количество золотых монет в $$$i$$$-м мешке.
Третья строка содержит $$$n$$$ целых чисел $$$b_1, b_2, \dots, b_n$$$ ($$$0 \le b_i \le 10^6$$$) — количество серебряных монет в $$$i$$$-м мешке.
Далее следуют $$$q$$$ строк запросов. $$$j$$$-я из следующих $$$q$$$ строк содержит два целых числа $$$l_j$$$ и $$$r_j$$$ ($$$1 \le l_j \le r_j \le n$$$) — описание $$$j$$$-го запроса.
Дополнительные ограничения на входные данные:
Для каждого запроса выведите одно целое число — вероятность того, что суммарная ценность монет в мешках с $$$l$$$ по $$$r$$$ строго больше суммарной ценности во всех остальных мешках, взятое по модулю $$$998244353$$$.
Вероятность можно выразить в виде несократимой дроби $$$\frac{x}{y}$$$. Вы должны вывести значение $$$x \cdot y^{-1} \bmod 998244353$$$, где $$$y^{-1}$$$ — целое число, такое, что $$$y \cdot y^{-1} \bmod 998244353 = 1$$$.
2 21 00 22 21 1
748683265 748683265
4 32 3 4 51 0 7 33 32 31 4
997756929 273932289 1
В обоих запросах из первого примера ответ равен $$$\frac{1}{4}$$$.
Название |
---|