/ 
Time Limit: 2.5 sec / Memory Limit: 1024 MB
配点 : 700 点
問題文
AtCoder 街道は、平らな地面の上に伸びる数直線で表される道路です。この道路上に N 個の高さ H の電柱が立っています。電柱には 1, 2, \dots, N の番号が古い順に付けられています。電柱 i \ (1 \leq i \leq N) は座標 X_i に地面と垂直に立っています。電柱の最下部は地面に固定されています。ここで、電柱は十分に細いものとして考えます。
AtCoder 街道ではこれから N 回の地震が発生します。i 回目 (1 \leq i \leq N) の地震では、以下のことが起こります。
- 電柱 i がまだ倒れていない場合、それが数直線における左または右の方向に、それぞれ \frac{1}{2} ずつの確率で倒れる。
- 倒れようとしている電柱が、まだ倒れていない電柱に衝突した場合（電柱の最下部に衝突した場合を含む）、この電柱も同じ方向に倒れる。場合によってはこれが連鎖的に起こる。
ここで、1. で電柱がどちら方向に倒れるかは、他の電柱がどちら方向に倒れたかに関係しません。
以下の図は一回の地震での電柱の倒れ方の一例です。
地震対策のため、t = 1, 2, \dots, N それぞれについて、ちょうど t 回目の地震ですべての電柱が倒れた状態になる確率を 2^N 倍した値を 998244353 で割った余りを求めてください。なお、出力すべき値は整数になることが証明できます。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq H \leq 10^9
- 0 \leq X_i \leq 10^9 \ (1 \leq i \leq N)
- X_1, X_2, \dots, X_N はすべて異なる
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
N H X_1 X_2 \cdots X_N
出力
t = 1, 2, \dots, N についての答えをその順番で空白区切りで出力してください。
入力例 1
3 2 0 3 1
出力例 1
4 2 2
以下の図は、この入力例における電柱の倒れ方の可能性を示しています。図中の分数はその状態になる確率を示しています。
したがって、ちょうど 1, 2, 3 回目の地震ですべての電柱が倒れた状態になる確率は、それぞれ \frac{1}{2}, \frac{1}{4}, \frac{1}{4} です。これを 8 倍した 4, 2, 2 を出力しましょう。
入力例 2
4 10 10 55 20 45
出力例 2
0 4 4 8
以下の図は、この入力例における電柱の倒れ方の可能性を示しています。図中の分数はその状態になる確率を示しています。
したがって、ちょうど 1, 2, 3, 4 回目の地震ですべての電柱が倒れた状態になる確率は、それぞれ 0, \frac{1}{4}, \frac{1}{4}, \frac{1}{2} です。これを 16 倍した 0, 4, 4, 8 を出力しましょう。
入力例 3
8 1 5 0 6 3 8 1 7 2
出力例 3
0 64 32 48 24 28 28 32
ちょうど 1, 2, 3, 4, 5, 6, 7, 8 回目の地震ですべての電柱が倒れた状態になる確率は、それぞれ 0, \frac{1}{4}, \frac{1}{8}, \frac{3}{16}, \frac{3}{32}, \frac{7}{64}, \frac{7}{64}, \frac{1}{8} です。
入力例 4
40 20 695 793 11 502 114 861 559 4 212 609 894 435 429 94 91 258 161 45 33 605 673 634 629 163 283 826 409 84 507 548 31 248 588 340 357 168 926 949 322 912
出力例 4
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 41942627 41942627 360709869
37 回目の地震までにすべての電柱が倒れることはありません。ちょうど 38, 39, 40 回目の地震ですべての電柱が倒れた状態になる確率は、それぞれ \frac{3}{8}, \frac{3}{8}, \frac{1}{4} です。
Score: 700 points
Problem Statement
AtCoder Street is a road represented by a straight line on flat ground. There are N utility poles of height H standing on this road. The poles are numbered 1, 2, \dots, N in chronological order. Pole i (1 \leq i \leq N) is vertically positioned at coordinate X_i. The base of each pole is fixed to the ground. Assume that the poles are sufficiently thin.
The street will experience N earthquakes. During the i-th earthquake (1 \leq i \leq N), the following events occur:
- If pole i has not yet fallen, it falls to the left or the right on the number line, each with a probability of \frac{1}{2}.
- If a falling pole collides with another pole that has not yet fallen (including collision at the base of the pole), the latter pole will also fall in the same direction. This may trigger a chain reaction.
The direction in which a pole falls during step 1 is independent of the direction in which other poles have fallen.
The following figure is an example of how poles might fall during one earthquake:
For earthquake preparedness, for each t = 1, 2, \dots, N, find the probability that all poles have fallen by exactly the t-th earthquake. Multiply it by 2^N and print the result modulo 998244353. It can be proved that the values to be printed are integers.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq H \leq 10^9
- 0 \leq X_i \leq 10^9 \ (1 \leq i \leq N)
- X_1, X_2, \dots, X_N are all distinct.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N H X_1 X_2 \cdots X_N
Output
Print the answers for t = 1, 2, \dots, N in this order, separated by spaces.
Sample Input 1
3 2 0 3 1
Sample Output 1
4 2 2
The following figure shows the possible ways the poles can fall for this sample input. The fractions in the figure indicate the probability of each state occurring.
Therefore, the probabilities that all poles have fallen by exactly the 1-st, 2-nd, 3-rd earthquakes are \frac{1}{2}, \frac{1}{4}, \frac{1}{4}, respectively. Multiply these by 8 to get 4, 2, 2 for output.
Sample Input 2
4 10 10 55 20 45
Sample Output 2
0 4 4 8
The following figure shows the possible ways the poles can fall for this sample input. The fractions in the figure indicate the probability of each state occurring.
Therefore, the probabilities that all poles have fallen by exactly the 1-st, 2-nd, 3-rd, 4-th earthquakes are 0, \frac{1}{4}, \frac{1}{4}, \frac{1}{2}, respectively. Multiply these by 16 to get 0, 4, 4, 8 for output.
Sample Input 3
8 1 5 0 6 3 8 1 7 2
Sample Output 3
0 64 32 48 24 28 28 32
The probabilities that all poles have fallen by exactly the 1-st, 2-nd, 3-rd, 4-th, 5-th, 6-th, 7-th, 8-th earthquakes are 0, \frac{1}{4}, \frac{1}{8}, \frac{3}{16}, \frac{3}{32}, \frac{7}{64}, \frac{7}{64}, \frac{1}{8}, respectively.
Sample Input 4
40 20 695 793 11 502 114 861 559 4 212 609 894 435 429 94 91 258 161 45 33 605 673 634 629 163 283 826 409 84 507 548 31 248 588 340 357 168 926 949 322 912
Sample Output 4
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 41942627 41942627 360709869
Not all poles will have fallen by the 37-th earthquake. The probabilities that all poles have fallen by exactly the 38, 39, 40-th earthquakes are \frac{3}{8}, \frac{3}{8}, \frac{1}{4}, respectively.