Rare Coins
Contest: Educational Codeforces Round 163 (Rated for Div. 2)
Difficulty rating: 2500
Tags: combinatorics, math, probabilities

There are $$$n$$$ bags numbered from $$$1$$$ to $$$n$$$, the $$$i$$$-th bag contains $$$a_i$$$ golden coins and $$$b_i$$$ silver coins.

The value of a gold coin is $$$1$$$. The value of a silver coin is either $$$0$$$ or $$$1$$$, determined for each silver coin independently ($$$0$$$ with probability $$$\frac{1}{2}$$$, $$$1$$$ with probability $$$\frac{1}{2}$$$).

You have to answer $$$q$$$ independent queries. Each query is the following:

- $$$l$$$ $$$r$$$ — calculate the probability that the total value of coins in bags from $$$l$$$ to $$$r$$$ is strictly greater than the total value in all other bags.

Input format:
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 3 \cdot 10^5$$$) — the number of bags and the number of queries, respectively.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^6$$$) — the number of gold coins in the $$$i$$$-th bag.

The third line contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$0 \le b_i \le 10^6$$$) — the number of silver coins in the $$$i$$$-th bag.

Next $$$q$$$ lines contain queries. The $$$j$$$-th of the next $$$q$$$ lines contains two integers $$$l_j$$$ and $$$r_j$$$ ($$$1 \le l_j \le r_j \le n$$$) — the description of the $$$j$$$-th query.

Additional constraints on the input:

- the sum of the array $$$a$$$ doesn't exceed $$$10^6$$$;
- the sum of the array $$$b$$$ doesn't exceed $$$10^6$$$.

Output format:
For each query, print one integer — the probability that the total value of coins in bags from $$$l$$$ to $$$r$$$ is strictly greater than the total value in all other bags, taken modulo $$$998244353$$$.

Formally, the probability can be expressed as an irreducible fraction $$$\frac{x}{y}$$$. You have to print the value of $$$x \cdot y^{-1} \bmod 998244353$$$, where $$$y^{-1}$$$ is an integer such that $$$y \cdot y^{-1} \bmod 998244353 = 1$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In both queries from the first example, the answer is $$$\frac{1}{4}$$$.

Example input:
2 2
1 0
0 2
2 2
1 1

Example output:
748683265 748683265

Example input:
4 3
2 3 4 5
1 0 7 3
3 3
2 3
1 4

Example output:
997756929 273932289 1

Editorial:
To calculate the probability, we will calculate the number of ways to assign values to silver coins in such a way that the total value inside the segment is greater than the total value outside.
Let define $$$x$$$ as the number of silver coins with value $$$1$$$ inside the segment, $$$y$$$ as the number of silver coins with value $$$1$$$ outside, $$$k$$$ as the difference between golden coins inside and outside the segment. Then the way to assign values to the coins is considered good if condition $$$x - y + k > 0$$$ is met.
We have an issue here: coins in the segment and coins outside the segment affect the inequality in different directions (that is, one of them increases the difference with a probability of $$$\frac{1}{2}$$$, while others decrease with a probability of $$$\frac{1}{2}$$$). It is not convenient for us.
So let's fix it, we can say that the coins inside the segment have value $$$1$$$ by default, and with a probability of $$$\frac{1}{2}$$$ are $$$0$$$. And the coins outside the segment have value of $$$0$$$ by default, and with a probability of $$$\frac{1}{2}$$$ are $$$1$$$. Then each of them, with a probability of $$$\frac{1}{2}$$$, reduces the difference "total in the segment minus total outside the segment" by $$$1$$$.
Thus, we have some starting value that decreases by $$$1$$$ with a probability of $$$\frac{1}{2}$$$ $$$m$$$ times (where $$$m$$$ is the total number of silver coins). And it is left to calculate the number of ways when the number of decreases is not big enough to break the inequality.
Let $$$cur$$$ be the number of silver coins inside the segment. Then the starting value is $$$st = k+cur$$$ and the number of ways to not break the inequality is equal to $$$sum = \sum\limits_{i=0}^{st-1} \binom{m}{i}$$$. And the answer to the problem is equal to $$$\frac{sum}{2^m}$$$.
Now we only need to consider how to answer queries faster than iterating from $$$0$$$ to $$$st$$$. But thanks to the fact that the value of $$$m$$$ is always the same, we can precalculate the prefix sums on these binomial coefficients.