AT_arc178_e.[ARC178E] Serval Survival

在一座长度为 $L$ 的桥上，有 $N$ 只薮猫。

第 $i$ 只薮猫位于距离桥左端 $A_{i}$ 的位置，满足 $0 < A_{1} < A_{2} < \cdots < A_{N} < L$。

对于 $i = 1, 2, \dots, N$，请回答以下问题。

薮猫们会依次进行以下 $3$ 个动作：

• 动作 $1$：除第 $i$ 只以外的 $N-1$ 只薮猫各自选择面向左或右。
• 动作 $2$：第 $i$ 只薮猫选择面向左或右。
• 动作 $3$：所有同时开始移动。每只以每单位时间恰好移动 $1$ 的速度前进。当薮猫到达桥的任一端时，会离开桥。当两只薮猫相遇时，双方都会反转前进方向并继续移动。

第 $i$ 只薮猫非常聪明，也很喜欢这座桥，因此在动作 $2$ 选择方向时，会观察其他 $N-1$ 只的朝向，并选择能让自己在动作 $3$ 中留在桥上的时间更长的方向。动作 $1$ 中，$N-1$ 只薮猫的朝向共有 $2^{N-1}$ 种组合。请你计算，对于所有这些组合，第 $i$ 只薮猫能留在桥上的最长时间之和，并对 $998244353$ 取模。可以证明，输出的结果一定是整数。

输入按以下格式从标准输入读入。

$N$ $L$

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

请输出 $N$ 行，第 $k$ 行为 $i=k$ 时的答案。

限制条件

• $1 \leq N \leq 10^{5}$
• $0 < A_{1} < A_{2} < \cdots < A_{N} < L \leq 10^{9}$
• 输入均为整数

样例解释 1

当 $i=1$ 时，始终面向右是最优的。当 $i=2$ 时，选择与第 $1$ 只薮猫相反的方向是最优的。

由 ChatGPT 4.1 翻译