問題文

P を素数 998244353 とします。 多項式 f(x) に対して次の一連の操作を定めます。

1. f(x) と (1 + x^k)g(x) の各次数の係数を P で割った余りが等しくなるような正の整数 k と有限次の多項式 g(x)\neq 0 を選択する。
2. その後、f(x) を上記の g(x) に置き換えて 2^k のスコアを得る。

ある多項式に対して、この操作を好きな回数行って得られるスコアの総和の最大値を多項式の 美しさ と定めます。

数列 A=(A_0,\ldots,A_{N - 1}) と Q 個のクエリが与えられます。

i 番目のクエリでは整数 l_i,r_i が与えられるので、多項式 \displaystyle f(x) = \sum_{j=0}^{r_i - l_i}A_{j + l_i}x^{j} の 美しさ を P で割った余りを求めてください。

ただし、操作における g(x) の係数は 998244353 未満の非負整数に限ります。(13:10 追記)

制約

• 入力は全て整数
• 2\leq N \leq 2000
• 1\leq Q \leq 2000
• 0\leq A_i < P
• 0\leq l_i < r_i \leq N - 1

入力例 1

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

出力例 1

4
6
0

1つめのクエリについて、f(x) = (1 + 2x + x^2) になりますが、 k = 1 を二回選択するのが最善です。

2つめのクエリについて、f(x) = (1 + x + x^2 + x^3)となりますが、 一回目の操作でk = 1、二回目の操作でk = 2 を選択するのが最善です。

3つめのクエリについて、f(x) = (1 + x + x^2)となりますが、一回も操作を行えません。

入力例 2

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

出力例 2

514
0

1つめのクエリでは、f(x) = (1 + x + x^9 + x^{10}) の美しさを計算し、2つめのクエリでは、f(x) = 0 の美しさを計算します。