分数: 1000 点
问题陈述
有 N 长桥上的薮猫 L.
的 i第一个薮猫位于位置 A_{i} 从桥的左端开始。
在这里, 0 < A_{1} < A_{2} < \cdots < A_{N} < L 成立。
对于每个 i = 1, 2, \dots, N,回答以下问题:
薮猫将按顺序执行以下三个动作:
- 行动 1: N - 1 薮猫以外 i第一个薮猫面向左或向右。
- 行动 2: i第一个薮猫面向左或右。
- 行动 3:所有薮猫同时开始移动。所有的薮猫都以恒定的速度移动 1 单位时间单位距离。当薮猫到达桥的尽头时,它就会离开桥。如果两只薮猫发生碰撞,它们都会改变方向并继续移动。
的 i第一个薮猫很聪明并且喜欢这座桥,所以在行动中选择方向时 2,它会观察对方的方向 N-1 薮猫并选择让它在行动期间在桥上停留更长时间的方向 3。 有 2^{N-1} 可能的方向组合 N-1 薮猫在行动 1。求总和,取模 998244353在所有这些组合中,持续时间 i第一个薮猫可以留在桥上。可以证明输出值是一个整数。
约束
- 1 \leq N \leq 10^{5}
- 0 < A_{1} < A_{2} < \cdots < A_{N} < L \leq 10^{9}
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N L
A_{1} A_{2} \cdots A_{N}
输出
打印 您选择的 N 行。的 k- 第行应包含以下问题的答案 i=k.
示例输入 1
2 167 9 24
示例输出 1
182 301
对于 i = 1,面朝右侧始终是最佳选择。
对于 i = 2,最好面向与第一批相反的方向。
示例输入 2
1 924 167
示例输出 2
757
示例输入 3
10 924924167 46001560 235529797 272749755 301863061 359726177 470023587 667800476 696193062 741860924 809211293
示例输出 3
112048251 409175578 167800512 997730745 278651538 581491882 884751575 570877705 747965896 80750577