你有 \(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\}\)

\(0< n,m\le 10^5, 0\le a_i\le 110000,0\le b_i\le 10^6\) 。