Score : $1000$ points

问题陈述

桥的长度为 $L$，上面有 $N$ 只薮猫。

第 $i$ 只薮猫位于桥的左端 $A_i$ 处。

这里满足 $0 < A_1 < A_2 < \cdots < A_N < L$。

对于每个 $i = 1, 2, \dots, N$，回答以下问题：

薮猫将按顺序执行以下三个动作：

• 动作 $1$：除了第 $i$ 只薮猫之外的 $N - 1$ 只薮猫面向左或右。
• 动作 $2$：第 $i$ 只薮猫面向左或右。
• 动作 $3$：所有薮猫同时开始移动。所有薮猫以每单位时间恰好 $1$ 单位距离的恒定速度移动。当一只薮猫到达桥的尽头时，它就离开桥。如果两只薮猫相撞，它们都改变方向并继续移动。

第 $i$ 只薮猫很聪明，喜欢这座桥，所以在动作 $2$ 中选择方向时，它会观察其他 $N-1$ 只薮猫的方向，并选择在动作 $3$ 中能让它在桥上停留更长时间的方向。在动作 $1$ 中，$N-1$ 只薮猫有 $2^{N-1}$ 种可能的方向组合。找出所有这些组合中，第 $i$ 只薮猫能在桥上停留的持续时间的总和，对 $998244353$ 取模。可以证明输出值是一个整数。

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

There are $N$ servals on a bridge of length $L$.

The $i$-th serval is located at position $A_{i}$ from the left end of the bridge.

Here, $0 < A_{1} < A_{2} < \cdots < A_{N} < L$ holds.

For each $i = 1, 2, \dots, N$, answer the following question:

The servals will perform the following three actions in order:

• Action $1$: The $N - 1$ servals other than the $i$-th serval face left or right.
• Action $2$: The $i$-th serval faces left or right.
• Action $3$: All servals start moving simultaneously. All servals move at a constant speed of exactly $1$ unit distance per unit time. When a serval reaches the end of the bridge, it leaves the bridge. If two servals collide, they both reverse their direction and continue moving.

The $i$-th serval is smart and loves this bridge, so when choosing a direction in Action $2$, it will observe the directions of the other $N-1$ servals and choose the direction that allows it to stay on the bridge the longer during Action $3$. There are $2^{N-1}$ possible combinations of directions for the $N-1$ servals in Action $1$. Find the sum, modulo $998244353$, over all these combinations, of the durations the $i$-th serval can stay on the bridge. It can be proved that the output value is an integer.

Constraints

• $1 \leq N \leq 10^{5}$
• $0 < A_{1} < A_{2} < \cdots < A_{N} < L \leq 10^{9}$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$ $L$

$A_{1}$ $A_{2}$ $\cdots$ $A_{N}$

Output

Print $N$ lines. The $k$-th line should contain the answer for $i=k$.

Sample Input 1

2 167
9 24

Sample Output 1

182
301

For $i = 1$, it is always optimal to face right.

For $i = 2$, it is optimal to face the opposite direction from the first serval.

Sample Input 2

1 924
167

Sample Output 2

757

Sample Input 3

10 924924167
46001560 235529797 272749755 301863061 359726177 470023587 667800476 696193062 741860924 809211293

Sample Output 3

112048251
409175578
167800512
997730745
278651538
581491882
884751575
570877705
747965896
80750577