No contest Total Champion!

問題文

全ファン待望の新作レースゲーム「モグビィのモグライダー」に収録されているモード「ワールドトライアル」では、参加するプレイヤー全員が広大なフィールドを駆け巡ってマシンを強化し、最後に登場する複数のスタジアムの中からそれぞれ選んだスタジアムに入りそのスタジアムの中にいる人たち全員で対戦する。もし、同じスタジアムを選んだプレイヤーが1人しかいない場合、そのプレイヤーは 戦わずして完全王者！ となる。

今、moguさんと $N$ 人のプレイヤーがワールドトライアルをプレイしている。戦わずして完全王者！ を目指しているmoguさんは次の情報を集めた。

• 最後に登場するスタジアムは $M$ 種類である。
• moguさん以外の $N$ 人のプレイヤーについて、 プレイヤー $i$ は スタジアム $l_i,l_i+1,...,r_i$ のいずれか $1$ つを選んで入ろうとしている。$(1 \leq i \leq N,1 \leq l_i \leq r_i \leq M)$

moguさんは、この情報をもとに、$M$ 種類のスタジアムのうち いずれか $1$ つを選んで入る。ここでmoguさん以外の各プレイヤーについて、そのプレイヤーは入ろうとしている各スタジアムの中から等確率でランダムに $1$ つ選んで入るものとする。

各 $j (1 \leq j \leq M)$ について、moguさんがスタジアム $j$ に入ったときに 戦わずして完全王者！ となる確率を $mod 998244353$ で求めよ。

• 確率を $mod 998244353$ で求めよ とは

この問題における確率は必ず有理数になることが証明できる。また、この問題の制約において、求める確率を既約分数 $\frac{y}{x}$ で表したときに $x$ が $998244353$ で割り切れないことが保証される。

このとき、$xz \equiv y (mod 998244353)$ を満たすような整数 $z (0 \leq z \leq 998244352)$ が一意に定まる。この $z$ を求めよ。

制約

• $1 \leq N,M \leq 10^5$
• $1 \leq l_i \leq r_i \leq M(1 \leq i \leq N)$

入力

入力はすべて整数である。

N M
l_1 r_1
l_2 r_2
...
l_N r_N

出力

各 $j (1 \leq j \leq M)$ について、moguさんがスタジアム $j$ に入ったときに 戦わずして完全王者！ となる確率を $mod 998244353$ で求めた値を1行づつ出力せよ。

サンプル

3 5
1 4
3 5
4 5

249561089
249561089
499122177
748683265
332748118

例えば、moguさんがスタジアム $2$ に入ったとき、 他にスタジアム $2$ に入る可能性があるのはプレイヤー $1$ で、 その確率は $\frac{1}{4}$ です。よって求める確率は $1-\frac{1}{4} = \frac{3}{4}$ となります。 また、moguさんがスタジアム $5$ に入ったとき、 他にスタジアム $5$ に入る可能性があるのはプレイヤー $2,3$ で、 その確率はそれぞれ $\frac{1}{3},\frac{1}{2}$ です。 よって、求める確率は $(1-\frac{1}{3})\times(1-\frac{1}{2})=\frac{1}{3}$ となります。

1 2
2 2

1
0

moguさんがスタジアム $1$ に入ったとき、他にスタジアム $1$ に入るプレイヤーはいません。よって、あなたに敵はいなかった！大勝利です！