Description

deepl翻译

有 $n$ 个袋子，编号从 $1$ 到 $n$ ， $i$ 个袋子里有 $a_i$ 枚金币和 $b_i$ 枚银币。

一枚金币的价值是 $1$ 。一枚银币的价值是 $0$ 或 $1$ ，由每枚银币独立决定（ $0$ 的概率是 $\frac{1}{2}$ ， $1$ 的概率是 $\frac{1}{2}$ ）。

您必须回答 $q$ 个独立的问题。每个问题如下：

• $l$ $r$ - 计算 $l$ 至 $r$ 袋中硬币的总价值严格大于所有其他袋中硬币总价值的概率。

Input

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

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$.

2 2
1 0
0 2
2 2
1 1

4 3
2 3 4 5
1 0 7 3
3 3
2 3
1 4

748683265 748683265

997756929 273932289 1

Note

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