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

В ряд расположено $$$n$$$ мешков, пронумерованных от $$$1$$$ до $$$n$$$; $$$i$$$-й мешок содержит $$$a_i$$$ золотых монет и $$$b_i$$$ серебряных монет.

Ценность золотой монеты равна $$$1$$$. Ценность серебряной монеты равна $$$0$$$ или $$$1$$$, и определяется для каждой серебряной монеты независимо ($$$0$$$ с вероятностью $$$\frac{1}{2}$$$ и $$$1$$$ с вероятностью $$$\frac{1}{2}$$$).

Вам нужно ответить на $$$q$$$ независимых запросов. Каждый запрос имеет следующий формат:

  • $$$l$$$ $$$r$$$ — посчитайте вероятность того, что суммарная ценность монет в мешках с $$$l$$$ по $$$r$$$ строго больше суммарной ценности во всех остальных мешках.
Входные данные

Первая строка содержит два целых числа $$$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$$$-го запроса.

Дополнительные ограничения на входные данные:

  • сумма массива $$$a$$$ не превышает $$$10^6$$$;
  • сумма массива $$$b$$$ не превышает $$$10^6$$$.
Выходные данные

Для каждого запроса выведите одно целое число — вероятность того, что суммарная ценность монет в мешках с $$$l$$$ по $$$r$$$ строго больше суммарной ценности во всех остальных мешках, взятое по модулю $$$998244353$$$.

Вероятность можно выразить в виде несократимой дроби $$$\frac{x}{y}$$$. Вы должны вывести значение $$$x \cdot y^{-1} \bmod 998244353$$$, где $$$y^{-1}$$$ — целое число, такое, что $$$y \cdot y^{-1} \bmod 998244353 = 1$$$.

Примеры
Входные данные
2 2
1 0
0 2
2 2
1 1
Выходные данные
748683265 748683265
Входные данные
4 3
2 3 4 5
1 0 7 3
3 3
2 3
1 4
Выходные данные
997756929 273932289 1
Примечание

В обоих запросах из первого примера ответ равен $$$\frac{1}{4}$$$.