Problem Statement

When a sequence $B$ is input, the Left Addition Machine repeats the following operation until the number of elements of $B$ becomes $1$, and then outputs the $1$ remaining element.

• Among the terms of $B$ that take the maximum value, select the leftmost one. (Here, suppose it is the $i$-th term from the left.) For every $j$ satisfying $1 \le j < i$, perform $B_j := B_j + B_i$ $1$ time each. (Add the $i$-th term of $B$ to the $j$-th term of $B$.) Then, delete the $i$-th term of $B$.

As input, a sequence $A$ of $N$ terms is given.

In addition, $Q$ queries are given. The $i$-th query is represented by the $2$ values $L_i,R_i$.

For each query, find the value output when $A_{L_i},A_{L_i+1}, \cdots , A_{R_i} $ (the contiguous subarray of $A$ from the $L_i$-th to the $R_i$-th term) is input to the Left Addition Machine, modulo $998244353$.

Note that the Left Addition Machine does not make any changes to $A$. That is, the queries are independent, and later queries are not affected by previously processed queries.

Input

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

• All inputs are integers.
• $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$

Output

On the $i$-th line, output the answer to the $i$-th query, followed by a newline.

Sample

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