← 返回题目列表

AtCoder · arc178_e

E. 薮猫生存

中文机器翻译题面 查看原题

分数: 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