Polynomial Derivatives Evaluation

You are given a polynomial of degree less than n:

$$F(x)=\sum_{i=0}^{n-1} f_i x^i$$

and m pairs \((a_i, k_i)\) satisfying $$\sum_{i=1}^m k_i=n.$$ For each pair \((a_i, k_i)\), you are required to compute the values of the derivatives of \(F(x)\) evaluated at \(a_i\): $$F^{(j)}(a_i)\quad \text{for}\quad 0 \le j < k_i,$$

where (F^{(j)}(x)) denotes the (j)-th derivative of (F(x)). All answers should be given modulo 998244353.

Note: The \(j\)-th derivative of \(F(x)=\sum_{i=0}^{n-1} f_i x^i\) is given by $$F^{(j)}(x)=\sum_{i=j}^{n-1} f_i \cdot \frac{i!}{(i-j)!}\, x^{i-j}.$$

## inputFormat

The input begins with a line containing two integers n and m (\(1 \le n \le 10^5\), \(1 \le m \le n\)), where n is the length of the polynomial (number of coefficients) and m is the number of query groups.

The second line contains n integers: f0, f1, ..., fn-1, representing the coefficients of \(F(x)\) (\(0 \le f_i < 998244353\)).

Then m lines follow. Each line contains two integers a and k representing a query group, where a is the evaluation point and k is the number of derivatives to compute. It is guaranteed that \(\sum_{i=1}^{m} k_i = n\).

## outputFormat

For each query group, output a single line containing k integers: the values of \(F^{(0)}(a), F^{(1)}(a), \ldots, F^{(k-1)}(a)\), each taken modulo 998244353.

## sample

5 2
1 2 3 4 5
1 2
2 3

15 38
151 160 32

$$