U - Recorder Editorial /

Time Limit: 12 sec / Memory Limit: 1024 MiB

配点 : 7 点

問題文

次の問題を 部分問題 と呼びます。

1 から N の番号がついた N 個の番組があります。番組 i は時刻 A_i から時刻 B_i まで放送しています。
あなたは 2 台の録画機を使って全ての番組を録画することにしました。
ここで、番組の集合 S について、1 台の録画機で S に含まれる番組を全て録画できる条件は、S に時間が被る番組の組が含まれないことです。(端点のみが被る場合は問題ないです。)

  • 厳密に述べると、ある S の異なる元 i, j であって \max(A_i, A_j) \lt \min(B_i, B_j) を満たすものが存在しない時に全ての番組を録画できます。

あなたは 2 台の録画機を使って全ての番組を録画することが可能ですか？厳密に述べると、番組の集合 \lbrace 1, 2, \dots, N \rbrace の分割 S_1, S_2 であって S_1 と S_2 がともに 1 台の録画機で全て録画可能である番組の集合であるようなものが存在しますか？
可能である場合は Yes を、そうでない場合は No を出力してください。

制約

  • 0 \leq A_i \lt B_i \leq T
  • N, T, A_i, B_i は整数

N および U が与えられます。T=1,2,\dots,U について次の問題を解いてください。

  • N, T が部分問題の N, T と同じ値だとする。この時、部分問題の入力としてあり得る (A_1, B_1), \dots, (A_N, B_N) は \left(\dfrac{T(T+1)}{2}\right)^N 通りあるが、そのうち部分問題の答えが Yes であるものの個数を 998244353 で割った余りを求めよ。

制約

  • 1 \leq N \leq 6 \times 10^4
  • 1 \leq U \leq 6 \times 10^4
  • N, U は整数

部分点

この問題には部分点が設定されている。

  • N \leq 5 \times 10^3 かつ U \leq 5 \times 10^3 を満たすデータセットに正解した場合、4 点が与えられる。

入力

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

N U

出力

U 行出力せよ。i 行目には T=i の時の答えを出力せよ。

入力例 1

3 4

出力例 1

0
12
114
558

T=2 の場合、(A_1, B_1) = (0, 2), (A_2, B_2) = (0, 1), (A_3, B_3) = (1, 2) のような入力が条件を満たします。

入力例 2

7 10

出力例 2

0
0
0
6300
260820
4161780
39414060
265208580
398083867
112841142

Score: 7 points

Problem Statement

We define the following as a subproblem:

There are N programs numbered 1 through N. Program i is broadcast from time A_i to time B_i.
You want to record all programs using 2 recorders.

For a set of programs S, the condition that all programs in S can be recorded by a single recorder is that no two programs in S overlap in time. (It is acceptable if they only touch at the endpoints.)

  • More formally, all programs in S can be recorded if there are no distinct i, j \in S such that \max(A_i, A_j) < \min(B_i, B_j) holds.

The question is whether it is possible to record all programs using 2 recorders.
More precisely, does there exist a partition S_1, S_2 of {1, 2, \dots, N} such that both S_1 and S_2 can each be recorded by a single recorder?
Output Yes if it is possible, otherwise output No.

Constraints:

  • 0 \leq A_i < B_i \leq T
  • N, T, A_i, B_i are integers

You are given N and U.
For each T = 1, 2, \dots, U, solve the following problem:

  • Suppose N, T are the same as in the subproblem. Then, the number of possible inputs (A_1, B_1), \dots, (A_N, B_N) is \left(\dfrac{T(T+1)}{2}\right)^N.
    Among them, count how many yield the answer Yes in the subproblem, and output the result modulo 998244353.

Constraints

  • 1 \leq N \leq 6 \times 10^4
  • 1 \leq U \leq 6 \times 10^4
  • N, U are integers

Partial Score

This problem has partial scoring:

  • If you solve all datasets with N \leq 5 \times 10^3 and U \leq 5 \times 10^3, you will earn 4 points.

Input

The input is given from standard input in the following format:

N U

Output

Print U lines. On the i-th line, output the answer for T = i.

Sample Input 1

3 4

Sample Output 1

0
12
114
558

For example, when T=2, an input such as (A_1, B_1) = (0, 2), (A_2, B_2) = (0, 1), (A_3, B_3) = (1, 2) satisfies the condition.

Sample Input 2

7 10

Sample Output 2

0
0
0
6300
260820
4161780
39414060
265208580
398083867
112841142