定義

この問題では、$0, 1, \dots, M-1$ を並び替えた数列 $P=(P_1,P_2,\dots,P_M)$ が $0$ 以上 $M-1$ 以下の整数 $x$ と $1$ 以上 $M-1$ 以下の整数 $y$ を用いて以下の漸化式で表せるとき、数列 $P$ を 初項 $x$ 公差 $y$ の等差順列、もしくは単に等差順列と呼びます。

$ P_{i} = \begin{cases} x & (i=1) \\ \left(P_{i-1} + y\right) \bmod M & (\mathrm{otherwise}) \end{cases} $

問題文

正整数 $N$, 素数 $M$, 長さ $N$ の数列 $B = (B_1,B_2,\dots,B_N), C = (C_1,C_2,\dots,C_N)$ が与えられます。

$K=1,2,\dots,N$ に対して以下の問題を解いてください。

問題

長さ $M$ の順列が $K$ 個あります。 $i$ 番目の順列を $A_i = (A_{i,1},A_{i,2},\dots,A_{i,M})$ で表すとし、 はじめ $A_i$ は初項 $B_i$ 公差 $C_i$ の等差順列です。

あなたは以下の操作を $0$ 回以上任意の回数行うことが出来ます。

• $1\le x < y \le K$ なる整数 $x,y$ と $1\le i < j \le M$ なる整数 $i,j$ を選択する。 $A_{x,i}$ と $A_{x,j}$ を入れ替え、 $A_{y,i}$ と $A_{y,j}$ を入れ替える。

操作を $0$ 回以上行った後の順列 $A_1,A_2,\dots,A_K$ の状態のうち、以下の条件を満たすものの個数を $\bmod998244353$ で求めてください。

条件
• 順列 $A_1,A_2,\dots,A_K$ は全て等差順列であり、互いに相異なる。

制約

• 入力は全て整数である。
• $2\le N \le 10^5$
• $2\le M \le 40009\ $(素数)
• $M$ は素数である。
• $0\le B_i < M$
• $1\le C_i < M$

入力

$N\ M$
$B_1\ C_1$
$B_2\ C_2$
$\vdots$
$B_N\ C_N$

出力

出力は $N$ 行からなる。

$i(1\le i\le N)$ 行目には $K = i$ の時の問題の答えを出力せよ。

サンプル

3 3
0 1
2 1
0 2

1
6
60

7 29
3 1
4 1
5 9
2 6
5 3
5 8
9 7

1
812
266705460
144923472
504663788
985419457
834752953