Problem Description

Let $ P $ be the prime number $ 998244353 $. For a polynomial $ f(x) $, we define a series of operations as follows:

1. Choose a positive integer $ k $ and a finite polynomial $g(x) \neq 0$ such that the coefficients of each degree of $ f(x) $ and $ (1 + x^k)g(x) $ are congruent modulo $ P $.
2. Then, replace $ f(x) $ with the above $ g(x) $ and gain a score of $ 2^k $.

The maximum sum of scores obtainable by performing this operation any number of times on a polynomial is defined as the polynomial's beauty.

You are given a sequence $A = (A_0, \ldots, A_{N-1})$ and $ Q $ queries.

For the $ i $-th query, you are given integers $ l_i, r_i $, and you need to find the beauty of the polynomial $\displaystyle f(x) = \sum_{j=0}^{r_i - l_i} A_{j + l_i}x^{j}$ modulo $ P $.

Note that the coefficients of $ g(x) $ in the operation must be non-negative integers less than $ 998244353 $. (Added at 13:10)

Input Format

The input is given from the standard input in the following format:

$ N $ $ Q $ $ A_{0} $ $\ldots$ $ A_{N-1} $ $ l_1 $ $ r_1 $ $\vdots$ $ l_{Q} $ $ r_{Q} $

Output Format

Output $ Q $ lines.

For each $ i $ $(1 \leq i \leq Q)$, output the answer to the $ i $-th query on the $ i $-th line.

Sample Input and Output

Sample Input #1

6 3
1 2 1 1 1 1
0 2
2 5
2 4

Sample Output #1

4
6
0

Sample Input #2

11 2
1 1 0 0 0 0 0 0 0 1 1
0 10
4 5

Sample Output #2

514
0

Notes/Hints

Constraints

• All inputs are integers.
• $2 \leq N \leq 2000$
• $1 \leq Q \leq 2000$
• $0 \leq A_i$
• $0 \leq l_i < r_i \leq N - 1$

Sample Explanation 1

For the first query, $ f(x) = (1 + 2x + x^2) $, the best strategy is to choose $ k = 1 $ twice. For the second query, $ f(x) = (1 + x + x^2 + x^3) $, the best strategy is to choose $ k = 1 $ in the first operation and $ k = 2 $ in the second operation. For the third query, $ f(x) = (1 + x + x^2) $, no operations can be performed.

Sample Explanation 2

For the first query, calculate the beauty of $ f(x) = (1 + x + x^9 + x^{10}) $. For the second query, calculate the beauty of $ f(x) = 0 $.

见题面 Input 部分

见题面 Output 部分