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

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

见题面 Input 部分

见题面 Output 部分

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