Problem Description

Given an **increasing** sequence $A$ of length $m$.

There are $q$ queries, each given $N, R$, calculate:

$$\left(\sum_{i=1}^R \binom{N}{A_i}\right) \bmod {998244353}$$

Input

The first line of the input contains two integers $m, q$ ($1 \le m, q < 2 ^ {17}$) - the length of $A$ and the number of queries.

The second line contains $m$ integers $A_1, A_2, \dots, A_m$ ($1 \le A_1 < A_2 < \dots < A_m < 2 ^ {17}$).

Each of the following $q$ lines contains two integers $N, R$ ($1 \le N \le 10 ^ 9$, $1 \le R \le m$).

Output

For each query, print a single integer - the answer of the query, modulo $998244353$.

6 10
2 4 5 6 8 10
5 2
5 1
4 3
8 5
5 2
5 1
10 6
7 6
6 2
8 6

15
10
7
183
15
10
763
84
30
183

Hint

There is a template for polynomial operations in [this link](https://paste.ubuntu.com/p/ppX3GhvKYN/).