题目描述

给定一个低于 $n$ 次的多项式 $F(x)=\displaystyle \sum_{i=0}^{n-1}f_ix^i$，以及 $m$ 组 $(a_i,k_i)$，满足 $\displaystyle \sum_{i=1}^m k_i=n$。

对于每一组 $(a_i,k_i)$，请求出 $F^{(j)}(a_i),\forall\, 0\le j< k_i$，答案对 $998244353$ 取模。

其中 $F^{(i)}(x)$ 代表 $F(x)$ 的 $i$ 阶导。

输入格式

第一行两个正整数 $n,m$。

第二行 $n$ 个整数，依次为 $f_0,f_1,\cdots ,f_{n-1}$。

接下来的 $m$ 行中，第 $i$ 行代表 $a_i,k_i$ 的值。

输出格式

输出共 $m$ 行。

第 $i$ 行有 $k_i$ 个数字，依次代表 $F(a_i),F'(a_i),F^{(2)}(a_i),\cdots ,F^{(k_i-1)}(a_i)$ 的值。

答案对 $998244353$ 取模。

11 11
18 2 6 17 7 19 17 6 2 12 14
1 1
2 1
3 1
4 1
5 1
6 1
7 1
8 1
9 1
10 1
11 1

120
23750
1107240
18147258
161737928
973451550
464732548
722342802
682083299
545845982
686473504

11 4
18 2 6 17 7 19 17 6 2 12 14
4 2
15 3
5 2
20 4

18147258 44343650 
804760733 115057816 300031140 
161737928 317914212 
73381527 279355195 666843568 217219267

提示

对于所有数据，$1\le m\le n\le 64000$，$0\le f_i,a_i<998244353$。

保证 $k_i$ 为正整数且 $\displaystyle \sum_{i=1}^mk_i =n$。

保证 $a_i$ 互不相同。