题目描述

UPDATE: 数据已修复，参考题面中的数据范围即可。

你有 $m$ 种物品，第 $i$ 种物品的大小为 $a_i$，数量为 $b_i$（$b_i=0$ 表示有无限个）。

你还有 $n$ 个背包，体积分别为 $1$ 到 $n$，现在你很想知道用这些物品填满某个背包的方案数。

为了满足你的好奇心，你决定把填满每个背包的方案数都算一遍。

因为你其实只是闲得无聊，所以你只想知道方案数对 $998244353$（$7\times 17\times 2^{23}+1$，一个质数）取模后的值。

输入格式

第一行两个非负整数，分别表示 $n,m$。

以下 $m$ 行，每行两个非负整数，分别表示 $a_i,b_i$。

输出格式

输出 $n$ 个非负整数表示答案。

5 3
1 0
1 1
3 2

2
2
3
4
4

拼出 $1$~$5$ 的方案分别如下：

$\{1_1\},\{1_2\}$

$\{1_1,1_1\},\{1_1,1_2\}$

$\{1_1,1_1,1_1\},\{1_1,1_1,1_2\},\{3\}$

$\{1_1,1_1,1_1,1_1\},\{1_1,1_1,1_1,1_2\},\{1_1,3\},\{1_2,3\}$

$\{1_1,1_1,1_1,1_1,1_1\},\{1_1,1_1,1_1,1_1,1_2\},\{1_1,1_1,3\},\{1_1,1_2,3\}$

数据范围与提示

$1 \le n \le 10^5,\, 0 \le m \le 10^5,\, 1\le a_i\le n,\, 0\le b_i\le 10^6$。