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: The first line contains two integers n and q ( 1 <= n, q <= 3 cdot 10^5 ) -- the number of bags and the number of queries, respectively. The second line contains n integers a_1, a_2, ... , a_n ( 0 <= a_i <= 10^6 ) -- the number of gold coins in the i -th bag. The third line contains n integers b_1, b_2, ... , b_n ( 0 <= b_i <= 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 <= l_j <= r_j <= n ) -- the description of the j -th query. Additional constraints on the input: 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 . In both queries from the first example, the answer is frac{1}{4} .