問題文

あなたは $N$ 個の魔法のアイテムを持っています．各アイテム $i$ ($1 \le i \le N$) には，倍率 $d_i$ と 魔力 $c_i$ が設定されています．

あなたはこれらのアイテムの中から，好きな組み合わせ（空集合を含む）を選んで装備することができます．あるアイテムの集合 $S \subseteq \{1, 2, \dots, N\}$ を選んだとき，その「合計倍率」と「合計魔力」を以下のように定義します．

• 合計倍率 $D_S$： 選んだアイテムの倍率の総乗．すなわち $D_S = \prod_{i \in S} d_i$．
• 合計魔力 $C_S$： 選んだアイテムの魔力の総乗．すなわち $C_S = \prod_{i \in S} c_i$．
  • ただし，空集合（$S = \emptyset$）の場合は $D_\emptyset = 1, C_\emptyset = 1$ とします．

各 $k = 1, 2, \dots, M$ について，合計倍率 $D_S$ がちょうど $k$ となるような全ての組み合わせ $S$ における「合計魔力 $C_S$」の総和を求めてください． 出力する値は，すべて $998,244,353$ で割った余りとします．

制約

• $1 \le N \le 10^5$
• $1 \le M \le 10^5$
• $1 \le d_i \le M$
• $0 \le c_i < 998,244,353$
• 入力はすべて整数である．

入力

入力は以下の形式で標準入力から与えられる．

出力

$M$ 行出力せよ．$k$ 行目には，合計倍率が $k$ となる組み合わせの魔力総和を $998,244,353$ で割った余りを出力すること．

サンプル

3 4
2 3
2 5
4 2

1
8
0
17

• $k=1$: 空集合のみ，魔力は 1．
• $k=2$: $\{アイテム1\}$ (魔力 3) と $\{アイテム2\}$ (魔力 5) の 2 通り，$3 + 5 = 8$．
• $k=3$: 合計倍率が 3 になる組み合わせは存在しない，0．
• $k=4$: $\{アイテム1, アイテム2\}$ (魔力 $3 \times 5 = 15$) と $\{アイテム3\}$ (魔力 2) の 2 通り，$15 + 2 = 17$．