問題文

Left Addition Machine は数列 $B$ を入力されると、以下の操作を $B$ の要素数が $1$ になるまで繰り返し、残った $1$ つの要素を出力します。

• $B$ の中で最大値を取る項のうち、最も左にあるものを選択する。(ここでは、左から$i$ 項目であったとする。)　$1 \le j < i$ を満たす全ての $j$ に関して、 $B_j := B_j + B_i$ をそれぞれ $1$ 回ずつ行う。($B$ の $j$ 項目に $B$ の $i$ 項目を加える。) その後、$B$ の $i$ 項目を削除する。

入力として、$N$ 項の数列 $A$ が与えられます。

加えて、 $Q$ 個のクエリが与えられます。 $i$ 番目のクエリは $L_i,R_i$ の $2$ 値で表されます。

各クエリに関して、 $A_{L_i},A_{L_i+1}, \cdots , A_{R_i}$ ( $A$ の $L_i$ から $R_i$ 項目までの連続部分列 )を Left Addition Machine に入力した場合に出力される値を $998244353$ で割った余りを答えてください。

なお、Left Addition Machineは $A$ に変更を加えることはありません。すなわち、各クエリは独立であり、前に処理したクエリによって後のクエリが影響を受けることはありません。

入力

$N\ Q$
$A_1\ A_2\ ...\ A_N$
$L_1\ R_1$
...
$L_Q\ R_Q$

• 入力は全て整数
• $1 \le N \le 2 \times 10^5$
• $1 \le Q \le 2 \times 10^5$
• $0 \le A_i < 998244353$
• $1 \le L_i \le R_i \le N$

出力

$i$ 行目には、 $i$ 番目のクエリに対する回答を出力し、改行してください。

サンプル

6 1
1 3 3 2 1 2
1 6

3

4 10
1 2 3 4
1 1
1 2
1 3
1 4
2 2
2 3
2 4
3 3
3 4
4 4

1
3
9
25
2
5
13
3
7
4

11 10
5 7 9 9 0 5 6 2 3 5 998244352
1 10
4 9
3 4
1 3
2 6
4 10
5 6
5 7
7 10
1 11

15
5
9
30
5
15
5
17
15
11